/***********************************************************************/
/* Open Visualization Data Explorer                                    */
/* (C) Copyright IBM Corp. 1989,1999                                   */
/* ALL RIGHTS RESERVED                                                 */
/* This code licensed under the                                        */
/*    "IBM PUBLIC LICENSE - Open Visualization Data Explorer"          */
/***********************************************************************/

#define ONLY_IN_GRAPH_LAYOUT_CODE 1
#include "GraphLayout.h"
#include "EditorWindow.h"
#include "ListIterator.h"
#include "Network.h"
#include "EditorWorkSpace.h"
#include "Node.h"
#include "StandIn.h"
#include "Ark.h"
#include "ArkStandIn.h"
#include "ErrorDialogManager.h"
#include "VPEAnnotator.h"
#include "DecoratorStyle.h"
#include "Dictionary.h"
#include <math.h>
//#include <limits.h> // for INT_MIN and INT_MAX
//
// How it works:
//
// ...in a nutshell: Traverse the graph assigning a hop count
// to each node computed as the number of hops from the top of
// the graph to reach the node.  Sort the graph by hop count.
// Among nodes that share a hop count, sort by the x coord
// of the nodes' arc's destination.  Iterate over the sorted
// lists placing nodes with output tab above input tab
// whereever possible.
//
// ...in more detail:
// - For each decorator creating a list of nodes sorted by
// increasing distance from the decorator.  This is used at
// the end of the layout so that I can place the decorator close
// to some node that it was close to before the layout started.
// - Tag every node with the number of hops required to reach
// the node from the top of the graph.  After that's computed
// I use that number * a constant to compute the node's y coord.
// For many nodes I tweak the tag after the initial computation
// because many nodes could really be represented by a variety
// of values.  Example: The max hop count from top to bottom
// of the graph is 5, but there's also an Input->Output.  The
// Input and Output nodes could be tagged 1,2 or 4,5.  Either
// is correct and it just depends on how you want things to
// look.
// - Create group data structures.  There is 1 group for every
// set of connected nodes.  In other words any 2 nodes that can
// be reached without lifting pen from paper are in the same
// group.
// - Sort the graph according to descending hop tag.
// - Perform the group's layout method starting from the
// beginning of the sorted list.  Within the group, create
// row data structures - 1 row for all nodes that share
// a hop tag.  The set of nodes placed in the layout method
// consists of all the nodes ABOVE the root node.
// - Perform the layout at the very bottom of the graph
// trivially by placing it at INITIAL_X,INITIAL_Y.
// - Perform each subsequent row's layout by sorting the
// nodes in the row by increasing x coord of the destination
// arc. The x coord is available after the preceeding row has
// been placed.
//

//
// ToDo:
// 1) When preparing the call to qsort() in LayoutRow there are some nodes
// that have 2 destination arcs on the next lower row.  On behalf of those
// nodes,
// it would be nice to perform the sort and layout multiple times and measure
// the quality of the result.  Then choose the one that worked the best.
//

//
// How far should successive 'levels' of the graph be separated
//
int GraphLayout::HeightPerLevel = 90;
#define ABSOLUTE_MINIMUM_HEIGHT_PER_LEVEL 70
#define MAXIMUM_HEIGHT_PER_LEVEL 200

//
//
//
const char* GraphLayout::ErrorMessages[] = {
    "-autoLayoutHeight is outside the legal range [80 - 200]. (The default is "
    "90.)\n",
    "-autoLayoutGroupSpacing is outside the legal range [10 - 100]. (The "
    "default is 30.)\n",
    "-autoLayoutNodeSpacing is outside the legal range [5 - 100]. (The default "
    "is 15.)\n",
    NULL};

//
// Allow a resource to control the vertical spreading out
// If there HeightPerLevel were too small, then it would become
// impossible to lay anything out.
//
const char* GraphLayout::SetHeightPerLevel( int hpl )
{
  if ( ( hpl < ABSOLUTE_MINIMUM_HEIGHT_PER_LEVEL ) ||
       ( hpl > MAXIMUM_HEIGHT_PER_LEVEL ) )
  {
    return GraphLayout::ErrorMessages[0];
  }
  GraphLayout::HeightPerLevel = hpl;
  return NUL( const char* );
}

//
// Identify original location of a decorator with respect to its
// closes node.
//
#define DECORATOR_ABOVE 1
#define DECORATOR_BELOW 2
#define DECORATOR_LEFT 4
#define DECORATOR_RIGHT 8

//
// x distance to separate disconnected groups of nodes from each other
//
int GraphLayout::GroupSpacing = 30;
#define MINIMUM_HORIZONTAL_GROUP_SPACING 10
#define MAXIMUM_HORIZONTAL_GROUP_SPACING 100

const char* GraphLayout::SetGroupSpacing( int gs )
{
  if ( ( gs < MINIMUM_HORIZONTAL_GROUP_SPACING ) ||
       ( gs > MAXIMUM_HORIZONTAL_GROUP_SPACING ) )
  {
    return ErrorMessages[1];
  }
  GraphLayout::GroupSpacing = gs;
  return NUL( const char* );
}

//
// When attempting to position nodes, we always check for collisions.
// In most cases there should never be any.  Only when merging two
// chunks of the same graph can it happen, but we check for it.  If
// there would be one then we place somewhere else.  Note: if you
// perform the layout, but find the Ctrl-U can't undo because it
// produces a warning message, the problem is probably that there
// was a collision when placing nodes.  The undo feature won't move
// nodes if doing so would cause bumper cars.
// Currently unused
#define COLLISION_OFFSET 15

//
// Leave a little extra horizontal room between standins because
// crowded levels must still allow lines to pass.
// We'll allow REQUIRED_ if that will let us make straight arcs
// but if we can't make straight arcs, then we'll offset by
// DESIRED_
//
#define REQUIRED_HSEP 5
#define MINIMUM_DESIRED_HSEP 5
#define MAXIMUM_DESIRED_HSEP 100
int GraphLayout::NodeSpacing = 15;
const char* GraphLayout::SetNodeSpacing( int ns )
{
  if ( ( ns < MINIMUM_DESIRED_HSEP ) || ( ns > MAXIMUM_DESIRED_HSEP ) )
  {
    return ErrorMessages[2];
  }
  GraphLayout::NodeSpacing = ns;
  return NUL( const char* );
}

//
// Starting coords for graph placement.  They have no meaning.  They
// just shouldn't get negative or greater than 64K since they might
// get stored into an unsigned short.
//
#define INITIAL_X 0  // 5000
#define INITIAL_Y 0  // 5000

//#define DEBUG_PLACEMENT
#if defined( DEBUG_PLACEMENT )
//
// $ setenv DEBUG_PLACEMENT
// in order to use this.
//
static boolean debug = FALSE;
#endif

//
// Comparator function used with qsort.  It says we're going to sort things
// by decreasing hop count. So the things early in the list are at the bottom
// of the graph.
//
int NodeInfo::SortByHop( const void* a, const void* b )
{
  Node** aptr = (Node**)a;
  Node** bptr = (Node**)b;
  Node* anode = (Node*)*aptr;
  Node* bnode = (Node*)*bptr;
  NodeInfo* ainfo = (NodeInfo*)anode->getLayoutInformation();
  NodeInfo* binfo = (NodeInfo*)bnode->getLayoutInformation();

  // descending order of hop count
  if ( ainfo->hops > binfo->hops )
    return -1;
  if ( ainfo->hops < binfo->hops )
    return 1;

  //
  // If the 2 nodes connect to different outputs of the same parent,
  // then sort by that.  Different strategies to try:
  // 1) output 1 1st, output 2 2nd, etc...
  // 2) middle output 1st, 1 left 2nd, 1 right 3rd, 2 left 4th, etc...
  // 3) odd numbered outputs first, then even numbered outputs.  This
  //    might produce a few straight lines.
  //
  boolean shares_output1;
  Ark* ark1 =
      GraphLayout::IsSingleInputNoOutputNode( anode, shares_output1, FALSE );
  if ( ark1 )
  {
    boolean shares_output2;
    Ark* ark2 =
        GraphLayout::IsSingleInputNoOutputNode( bnode, shares_output2, FALSE );

    if ( ark2 )
    {
      Node* parent1, *parent2;
      int input1, input2;
      parent1 = ark1->getSourceNode( input1 );
      parent2 = ark2->getSourceNode( input2 );
      if ( parent1 == parent2 )
      {
        if ( input1 != input2 )
        {
          int output_count = parent1->getOutputCount();
          int middle = ( output_count >> 1 ) + 1;
          int diff1 = middle - input1;
          int diff2 = middle - input2;
          if ( diff1 < 0 )
            diff1 = -diff1;
          if ( diff2 < 0 )
            diff2 = -diff2;
          if ( diff1 < diff2 )
            return -1;
          if ( diff2 < diff1 )
            return 1;
        }
      }
    }
  }

  return 0;
}

void LayoutInfo::initialize( UIComponent* uic )
{
  ASSERT( uic );
  uic->getXYPosition( &this->orig_x, &this->orig_y );
  this->x = this->y = -1;
  uic->getXYSize( &this->w, &this->h );
  this->initialized = TRUE;
}

void NodeInfo::initialize( Node* n, int hops )
{
  n->setLayoutInformation( this );
  this->hops = hops;
  this->LayoutInfo::initialize( n->getStandIn() );
}

void AnnotationInfo::initialize( VPEAnnotator* dec )
{
  dec->setLayoutInformation( this );
  this->LayoutInfo::initialize( dec );
}

//
// This is the entry point for automatic graph layout.  This is a public
// method called from EditorWindow.
//
boolean GraphLayout::entireGraph( WorkSpace* workSpace, const List& nodes,
                                  const List& decorators )
{
  int offset;
  List nodeList;

#if defined( DEBUG_PLACEMENT )
  debug = ( getenv( "DEBUG_PLACEMENT" ) ? TRUE : FALSE );
#endif

  ListIterator li;
  boolean retval = TRUE;
  Node* n;

  // exclude the nodes that aren't in the current page
  li.setList( (List&)nodes );
  while ( ( n = (Node*)li.getNext() ) )
  {
    StandIn* si = n->getStandIn();
    if ( !si )
      continue;
    if ( si->getWorkSpace() != workSpace )
      continue;
    nodeList.appendElement( n );
  }

  //
  // Must store the nodes to reflow in an array because later
  // we're going to use qsort.
  //
  Node** reflow;
  int reflow_count = 0;
  int reflow_size = nodeList.getSize();
  reflow = (Node**)malloc( sizeof( Node* ) * reflow_size );
  li.setList( nodeList );
  while ( ( n = (Node*)li.getNext() ) )
  {
    reflow[reflow_count++] = n;
  }
  ASSERT( reflow_count == reflow_size );

  //
  // 1) For each node, record the hops required to reach the node
  //    from the top of the graph.  Optionally push nodes up or
  //    down as aesthetics require.
  //
  this->computeHopCounts( reflow, reflow_count );

  //
  // 2) Set up associations between annotations and nodes by finding
  // each annotation's nearest node.  This happens after computeHopCounts()
  // because we need to use the LayoutInfo that computeHopCounts() sets
  // up.
  //
  List decorators_in_current_page;
  int widest_decorator = 0;
  int tallest_decorator = 0;
  this->prepareAnnotationPlacement( decorators_in_current_page, reflow,
                                    reflow_count, decorators, workSpace,
                                    widest_decorator, tallest_decorator );

  //
  // 3) Sort the list in descending order of hop,ancestor counts.
  //    Internal nodes are placed according to the order in which
  //    they're wired to inputs.
  //
  qsort( reflow, reflow_count, sizeof( Node* ), NodeInfo::SortByHop );

  //
  // 4) Group the nodes.  Any 2 nodes that have a path between them
  //      go into the same group.
  //
  int next;
  for ( next = 0; next < reflow_count; next++ )
  {
    Node* n = reflow[next];
    NodeInfo* ni = (NodeInfo*)n->getLayoutInformation();
    List* connected = ni->getConnectedNodes( n );
    ListIterator iter( *connected );
    if ( ni->getLayoutGroup() )
      continue;
    LayoutGroup* group = new LayoutGroup( this->layout_groups.getSize() );
    this->layout_groups.appendElement( group );
    while ( ( n = (Node*)iter.getNext() ) )
    {
      NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
      info->setLayoutGroup( group );
    }
  }
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    for ( next = 0; next < reflow_count; next++ )
    {
      Node* n = reflow[next];
      NodeInfo* ni = (NodeInfo*)n->getLayoutInformation();
      LayoutGroup* group = ni->getLayoutGroup();
      ASSERT( group );
      fprintf( stdout, "%s[%d] %s hops=%d in group %d\n", __FILE__, __LINE__,
               n->getNameString(), ni->getGraphDepth(), group->getId() );
    }
  }
#endif

  //
  // 5) For the first node in the list, walk up the graph placing nodes.
  //
  n = reflow[0];

#if defined( DEBUG_PLACEMENT )
  if ( debug )
    fprintf( stdout, "%s[%d] %s placing\n", __FILE__, __LINE__,
             n->getNameString() );
#endif

  List positioned;
  NodeInfo* linfo = (NodeInfo*)n->getLayoutInformation();
  LayoutGroup* group = linfo->getLayoutGroup();
  group->layout( n, this, positioned );
  this->repositionNewPlacements( n, TRUE, positioned );

  //
  // 6) For each subsequent unmarked node in the list, walk up the graph
  //    until hitting a marked node.
  //
  for ( next = 1; next < reflow_count; next++ )
  {
    n = reflow[next];
    linfo = (NodeInfo*)n->getLayoutInformation();
    if ( linfo->isPositioned() )
      continue;

#if defined( DEBUG_PLACEMENT )
    if ( debug )
      fprintf( stdout, "%s[%d] %s placing...", __FILE__, __LINE__,
               n->getNameString() );
#endif

    //
    // Locate a connected, positioned node so that we can
    // get the right y coordinate.
    //
    List* connected = linfo->getConnectedNodes( n );
    ListIterator iter( *connected );
    Node* node;
    boolean separated = TRUE;
    int y;
    while ( ( node = (Node*)iter.getNext() ) )
    {
      NodeInfo* ninfo = (NodeInfo*)node->getLayoutInformation();
      if ( !ninfo->isPositioned() )
        continue;
      int dummy;
      ninfo->getXYPosition( dummy, y );
      separated = FALSE;
      int dd = ninfo->getGraphDepth() - linfo->getGraphDepth();
      y -= ( dd * GraphLayout::HeightPerLevel );
      break;
    }

    if ( !separated )
    {
#if defined( DEBUG_PLACEMENT )
      if ( debug )
        fprintf( stdout, " [%d] connected\n", __LINE__ );
#endif
      // The value 20000 isn't meaningful.  Its purpose is to
      // keep new node placments clear of existing node placements
      // because we want the new ones to get a decent arrangement
      // without colliding with others in the group.  After we've
      // finished this section of the graph, then we'll take all
      // the nodes just placed and move them as a group, to a better
      // location relative to the others in their group.
      linfo->setProposedLocation( 20000, y );
    }
    else
    {
#if defined( DEBUG_PLACEMENT )
      if ( debug )
        fprintf( stdout, " [%d] disconnected", __LINE__ );
#endif
      // There was no positioned connected node. We are
      // be working on a disconnected subgraph.
    }
    positioned.clear();
    group = linfo->getLayoutGroup();
    group->layout( n, this, positioned );

    this->repositionNewPlacements( n, separated, positioned );
#if defined( DEBUG_PLACEMENT )
    if ( debug )
      fprintf( stdout, "\n" );
#endif
  }

  //
  // 7) All nodes have now been divied up into groups.  Within groups,
  // the nodes have been positioned.  Each group is a set of nodes with
  // connections internal to the group.  Now it's time to position each
  // group.  This should be accomplished with respect shown to the arrangement
  // of the groups within the canvas before automatic layout was kicked
  // off.  This is what gives authors a measure of control over the
  // appearance of the result.
  //
  this->repositionGroups( reflow, reflow_count );

  //
  // 9) To apply placmenets, compute the bounding box of the nodes'
  //    placments, then translate so that all nodes have positive x,y
  //    and so that the center of the graph is near the center of the
  //    vpe if possible.
  //
  int minx, miny, maxx, maxy;
  this->computeBoundingBox( reflow, reflow_count, minx, miny, maxx, maxy );

  workSpace->beginManyPlacements();

  //
  // The curtain is almost ready to go up.  We must adjust the location of all
  // nodes to be close to the upper left corner of the canvas.  The vpe
  // annotation
  // still hasn't been placed, so we'll allow some extra room so that the
  // annotation
  // can be placed conveniently.
  //
  offset = MIN( widest_decorator, 200 );
  offset = MAX( offset, 10 );
  minx -= offset;
  offset = MIN( tallest_decorator, 200 );
  offset = MAX( offset, 10 );
  miny -= offset;

  int l;
  for ( l = 0; l < reflow_count; l++ )
  {
    int x, y;
    Node* n = reflow[l];
    LayoutInfo* linfo = (LayoutInfo*)n->getLayoutInformation();
    linfo->getXYPosition( x, y );
    x -= minx;
    y -= miny;
    linfo->setProposedLocation( x, y );
    // By uncommenting this line, I'm able to verify that everything
    // worked as planned.  I like this information but I don't
    // what it shown to users.
    // if (linfo->collided()) y+=COLLISION_OFFSET;
    this->editor->saveLocationForUndo( n->getStandIn(), FALSE, (boolean)l );
    n->setVpePosition( x, y );
  }

  this->repositionDecorators( decorators_in_current_page, (boolean)l, reflow,
                              reflow_count );

  //
  // 10) Rebuild all the arcs by fetching the workspace data structure,
  //    destroying it and creating a new one.  The workspace lines can
  //    be created and destroyed but never modified.
  //
  int k;
  for ( k = 0; k < reflow_count; k++ )
  {
    Node* n = reflow[k];
    int input_count = n->getInputCount();
    StandIn* si = n->getStandIn();
    int j;
    for ( j = 1; j <= input_count; j++ )
    {
      if ( !n->isInputVisible( j ) )
        continue;
      List* arcs = (List*)n->getInputArks( j );
      Ark* arc;
      ListIterator iter( *arcs );
      while ( ( arc = (Ark*)iter.getNext() ) )
      {
        ArkStandIn* asi = arc->getArkStandIn();
        delete asi;
        si->addArk( this->editor, arc );
      }
    }
  }
  workSpace->endManyPlacements();

cleanup:
  //
  // Each node will delete its NodeInfo
  //
  int i;
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    // deletes the layout information
    n->setLayoutInformation( NULL );
  }
  free( reflow );

  //
  // erase all the group records
  //
  ListIterator iter( this->layout_groups );
  LayoutGroup* g;
  while ( ( g = (LayoutGroup*)iter.getNext() ) )
    delete g;
  this->layout_groups.clear();

  //
  // each decorator will deletes its AnnotationInfo
  //
  VPEAnnotator* dec;
  iter.setList( decorators_in_current_page );
  while ( ( dec = (VPEAnnotator*)iter.getNext() ) )
  {
    dec->setLayoutInformation( NUL(AnnotationInfo*));
  }
  return retval;
}

void GraphLayout::unmarkAllNodes( Node* reflow[], int reflow_count )
{
  int i;
  for ( i = 0; i < reflow_count; i++ )
    reflow[i]->clearMarked();
}
boolean GraphLayout::hasConnectedInputs( Node* n )
{
  int input_count = n->getInputCount();
  int h;
  for ( h = 1; h <= input_count; h++ )
  {
    if ( !n->isInputVisible( h ) )
      continue;
    List* inputs = (List*)n->getInputArks( h );
    if ( !inputs )
      continue;
    if ( !inputs->getSize() )
      continue;
    return TRUE;
  }
  return FALSE;
}

boolean GraphLayout::hasConnectedOutputs( Node* n, Node* other_than )
{
  int dummy;
  int output_count = n->getOutputCount();
  int h;
  for ( h = 1; h <= output_count; h++ )
  {
    if ( !n->isOutputVisible( h ) )
      continue;
    List* outputs = (List*)n->getOutputArks( h );
    if ( !outputs )
      continue;
    if ( !outputs->getSize() )
      continue;
    if ( other_than )
    {
      boolean others_found = FALSE;
      ListIterator iter( *outputs );
      Ark* arc;
      while ( ( arc = (Ark*)iter.getNext() ) )
      {
        Node* destination = arc->getDestinationNode( dummy );
        if ( destination != other_than )
        {
          others_found = TRUE;
        }
      }
      if ( others_found )
        return TRUE;
      else
        continue;
    }
    return TRUE;
  }
  return FALSE;
}

//
// Returns true if the destination location is empty.  We need this because
// placing one StandIn on top of another leads to bumper cars.
//
boolean GraphLayout::nodeCanMoveTo( Node* n, int x, int y )
{
  NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
  List* connected_nodes = info->getConnectedNodes( n );

  int width, height;
  info->getXYSize( width, height );

  ListIterator iter( *connected_nodes );
  Node* target;
  int tw, th, tx, ty;
  while ( ( target = (Node*)iter.getNext() ) )
  {
    NodeInfo* target_info = (NodeInfo*)target->getLayoutInformation();
    if ( target_info == info )
      continue;
    if ( !target_info->isPositioned() )
      continue;
    target_info->getXYPosition( tx, ty );
    target_info->getXYSize( tw, th );
    if ( ( x > ( tx + tw ) ) || ( y > ( ty + th ) ) )
      continue;
    if ( ( ( x + width ) < tx ) || ( ( y + height ) < ty ) )
      continue;
#if defined( DEBUG_PLACEMENT )
    if ( debug )
    {
      fprintf( stdout, "%s[%d] %s movement to %d,%d conflicted with %s\n",
               __FILE__, __LINE__, n->getNameString(), x, y,
               target->getNameString() );
    }
#endif
    return FALSE;
  }
  return TRUE;
}

boolean GraphLayout::CanMoveTo( LayoutInfo* info, int x, int y, Node* reflow[],
                                int count, List* decorators )
{
  int width, height;
  info->getXYSize( width, height );

  int tw, th, tx, ty;
  int i;
  for ( i = 0; i < count; i++ )
  {
    Node* target = reflow[i];
    NodeInfo* target_info = (NodeInfo*)target->getLayoutInformation();
    if ( target_info == info )
      continue;
    if ( !target_info->isPositioned() )
      continue;
    target_info->getXYPosition( tx, ty );
    target_info->getXYSize( tw, th );
    if ( ( x > ( tx + tw ) ) || ( y > ( ty + th ) ) )
      continue;
    if ( ( ( x + width ) < tx ) || ( ( y + height ) < ty ) )
      continue;
    return FALSE;
  }
  if ( decorators )
  {
    ListIterator iter( *decorators );
    LayoutInfo* target_info;
    VPEAnnotator* dec;
    while ( ( dec = (VPEAnnotator*)iter.getNext() ) )
    {
      target_info = (LayoutInfo*)dec->getLayoutInformation();
      if ( target_info == info )
        continue;
      if ( !target_info->isPositioned() )
        continue;
      target_info->getXYPosition( tx, ty );
      target_info->getXYSize( tw, th );
      if ( ( x > ( tx + tw ) ) || ( y > ( ty + th ) ) )
        continue;
      if ( ( ( x + width ) < tx ) || ( ( y + height ) < ty ) )
        continue;
      return FALSE;
    }
  }
  return TRUE;
}

//
// Compute a location for the source node of arc.  The location should
// result in a straight wire from the source's output tab to the
// destination's input tab.
//
boolean GraphLayout::positionSourceOverDest( Ark* arc, int& x, int& y )
{
  int input, output;
  int dx, dy, sx, sy;
  int xincr, yincr;
  Node* destination = arc->getDestinationNode( input );
  Node* source = arc->getSourceNode( output );
  NodeInfo* src_info = (NodeInfo*)source->getLayoutInformation();
  NodeInfo* dst_info = (NodeInfo*)destination->getLayoutInformation();
  StandIn* src_si = source->getStandIn();
  StandIn* dst_si = destination->getStandIn();
  ASSERT( dst_info->isPositioned() );
  dst_info->getXYPosition( dx, dy );
  int dst_tab_x = dst_si->getInputParameterTabX( input );
  int src_tab_x = src_si->getOutputParameterTabX( output );
  sx = dx + ( dst_tab_x - src_tab_x );
  sy = dy + ( src_info->getGraphDepth() - dst_info->getGraphDepth() ) *
                GraphLayout::HeightPerLevel;

  boolean collided = ( this->nodeCanMoveTo( source, sx, sy ) == FALSE );

  x = sx;
  y = sy;
  return collided;
}

//
// Position the standIn so that the tab used by arc will have its line
// at the the specified x coord.
//
boolean GraphLayout::positionSource( Ark* arc, int xcoord_of_arc )
{
  int input, dummy, dx, dy, sx, sy;
  Node* destination = arc->getDestinationNode( dummy );
  Node* source = arc->getSourceNode( input );
  NodeInfo* src_info = (NodeInfo*)source->getLayoutInformation();
  NodeInfo* dst_info = (NodeInfo*)destination->getLayoutInformation();
  StandIn* src_si = source->getStandIn();
  ASSERT( dst_info->isPositioned() );
  dst_info->getXYPosition( dummy, dy );
  int half_tab_width = 9;
  sy = dy + ( src_info->getGraphDepth() - dst_info->getGraphDepth() ) *
                GraphLayout::HeightPerLevel;

  int src_tab_x = src_si->getOutputParameterTabX( input );
  sx = xcoord_of_arc - ( src_tab_x + half_tab_width );

  src_info->setProposedLocation( sx, sy );
  return ( this->nodeCanMoveTo( source, sx, sy ) == FALSE );
}

boolean GraphLayout::computeBoundingBox( Node* reflow[], int reflow_count,
                                         int& minx, int& miny, int& maxx,
                                         int& maxy, List* decorators )
{
  boolean valid_information = FALSE;
  minx = miny = 99999999;
  maxx = maxy = -99999999;
  int x, y, w, h;
  int i;
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    LayoutInfo* li = (LayoutInfo*)n->getLayoutInformation();
    ASSERT( li->isPositioned() );
    li->getXYPosition( x, y );
    li->getXYSize( w, h );
    if ( x < minx )
      minx = x;
    if ( y < miny )
      miny = y;
    if ( ( x + w ) > maxx )
      maxx = x + w;
    if ( ( y + h ) > maxy )
      maxy = y + h;
    valid_information = TRUE;
  }
  if ( decorators )
  {
    ListIterator iter( *decorators );
    VPEAnnotator* dec;
    while ( ( dec = (VPEAnnotator*)iter.getNext() ) )
    {
      LayoutInfo* info = (LayoutInfo*)dec->getLayoutInformation();
      info->getXYPosition( x, y );
      info->getXYSize( w, h );
      if ( x < minx )
        minx = x;
      if ( y < miny )
        miny = y;
      if ( ( x + w ) > maxx )
        maxx = x + w;
      if ( ( y + h ) > maxy )
        maxy = y + h;
    }
  }
  return valid_information;
}

boolean GraphLayout::computeBoundingBox( List& nodes, int& minx, int& miny,
                                         int& maxx, int& maxy )
{
  boolean valid_information = FALSE;
  minx = miny = 99999999;
  maxx = maxy = -99999999;
  ListIterator li( nodes );
  Node* n;
  while ( ( n = (Node*)li.getNext() ) )
  {
    LayoutInfo* linfo = (LayoutInfo*)n->getLayoutInformation();
    ASSERT( linfo->isPositioned() );
    int x, y, w, h;
    linfo->getXYPosition( x, y );
    linfo->getXYSize( w, h );
    if ( x < minx )
      minx = x;
    if ( y < miny )
      miny = y;
    if ( ( x + w ) > maxx )
      maxx = x + w;
    if ( ( y + h ) > maxy )
      maxy = y + h;
    valid_information = TRUE;
  }
  return valid_information;
}

void GraphLayout::repositionDecorators( List& decorators, boolean sef,
                                        Node* reflow[], int reflow_count )
{
  int minx, miny, maxx, maxy;
  this->computeBoundingBox( reflow, reflow_count, minx, miny, maxx, maxy );
  AnnotationInfo::NextX = maxx + 4;
  AnnotationInfo::NextY = 10;
  ListIterator decs( decorators );
  boolean same_event_flag = sef;
  int decx, decy;
  VPEAnnotator* dec;
  while ( ( dec = (VPEAnnotator*)decs.getNext() ) )
  {
    this->editor->saveLocationForUndo( dec, FALSE, same_event_flag );
    same_event_flag = TRUE;
    AnnotationInfo* ainfo = (AnnotationInfo*)dec->getLayoutInformation();
    ainfo->reposition( reflow, reflow_count, decorators );
    ainfo->getXYPosition( decx, decy );
    dec->setXYPosition( decx, decy );
  }
}

boolean GraphLayout::IsSingleOutputNoInputNode( Node* n )
{
  int i;
  int output_count = n->getOutputCount();
  int voc = 0;  // visible output count
  for ( i = 1; i <= output_count; i++ )
  {
    if ( n->isOutputVisible( i ) )
    {
      voc++;
      if ( voc > 1 )
        return FALSE;
    }
  }
  int input_count = n->getInputCount();
  Ark* arc;
  for ( i = 1; i <= input_count; i++ )
  {
    if ( !n->isInputVisible( i ) )
      continue;
    List* arcs = (List*)n->getInputArks( i );
    if ( !arcs )
      continue;
    if ( arcs->getSize() )
      return FALSE;
  }
  return TRUE;
}
Ark* GraphLayout::IsSingleInputNoOutputNode( Node* n, boolean& shares_an_output,
                                             boolean positioned )
{
  int output_count = n->getOutputCount();
  int output;
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !n->isOutputVisible( output ) )
      continue;
    List* outputs = (List*)n->getOutputArks( output );
    if ( !outputs )
      continue;
    if ( !outputs->getSize() )
      continue;
    return NULL;
  }

  int input_count = n->getInputCount();
  Ark* input_arc = NULL;
  Ark* arc;
  int input;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* inputs = (List*)n->getInputArks( input );
    if ( !inputs )
      continue;
    if ( !inputs->getSize() )
      continue;
    ListIterator arcs( *inputs );
    while ( ( arc = (Ark*)arcs.getNext() ) )
    {
      if ( !input_arc )
      {
        // test for the output has only 1 destination node
        int output;
        Node* source = arc->getSourceNode( output );
        List* outputs = (List*)source->getOutputArks( output );
        ASSERT( outputs );
        if ( outputs->getSize() != 1 )
        {
          shares_an_output = TRUE;
        }
        else
        {
          shares_an_output = FALSE;
        }
        if ( positioned )
        {
          LayoutInfo* linfo = (LayoutInfo*)source->getLayoutInformation();
          if ( !linfo->isPositioned() )
            break;
        }
        input_arc = arc;
      }
      else
      {
        return NULL;
      }
    }
  }
  return input_arc;
}

boolean GraphLayout::positionDestBesideSibling( Ark* arc, int& x, int& y,
                                                boolean left,
                                                List* unusable_nodes )
{
  int output, input, dummy;
  Node* source = arc->getSourceNode( output );
  Node* destination = arc->getDestinationNode( input );
  List* arcs = (List*)source->getOutputArks( output );
  ListIterator iter( *arcs );
  Ark* oa;
  while ( ( oa = (Ark*)iter.getNext() ) )
  {
    Node* dst = oa->getDestinationNode( dummy );
    if ( dst == destination )
      continue;

    // At this point, we've located a sibling.  Attempt a position
    // beside the standIn.
    NodeInfo* dinfo = (NodeInfo*)dst->getLayoutInformation();
    if ( !dinfo->isPositioned() )
      continue;

    // We cannot use a sibling if it's a member of the set of
    // nodes that we're trying to place.
    if ( unusable_nodes->isMember( dst ) )
      continue;

    int w, h;
    NodeInfo* info = (NodeInfo*)destination->getLayoutInformation();
    info->getXYSize( w, h );

    int sibling_x;
    dinfo->getXYPosition( sibling_x, y );
    if ( left )
    {
      x = sibling_x - ( w + GraphLayout::NodeSpacing );
    }
    else
    {
      int sibling_w;
      dinfo->getXYSize( sibling_w, dummy );
      x = sibling_x + sibling_w + GraphLayout::NodeSpacing;
    }
  }
  boolean collided = ( this->nodeCanMoveTo( destination, x, y ) == FALSE );
  return collided;
}

//
// Compute a location for the destination node of arc.  The location should
// result in a straight wire from the source's output tab to the
// destination's input tab.
//
boolean GraphLayout::positionDestUnderSource( Ark* arc, int& x, int& y )
{
  int input, output;
  int dx, dy, sx, sy;
  int xincr, yincr;
  Node* destination = arc->getDestinationNode( input );
  Node* source = arc->getSourceNode( output );
  NodeInfo* src_info = (NodeInfo*)source->getLayoutInformation();
  NodeInfo* dst_info = (NodeInfo*)destination->getLayoutInformation();
  StandIn* src_si = source->getStandIn();
  StandIn* dst_si = destination->getStandIn();
  ASSERT( src_info->isPositioned() );
  src_info->getXYPosition( sx, sy );
  int dst_tab_x = dst_si->getInputParameterTabX( input );
  int src_tab_x = src_si->getOutputParameterTabX( output );
  dx = sx + ( -dst_tab_x + src_tab_x );
  dy = sy + ( ( dst_info->getGraphDepth() - src_info->getGraphDepth() ) *
              GraphLayout::HeightPerLevel );
  boolean collided = ( this->nodeCanMoveTo( destination, dx, dy ) == FALSE );
  x = dx;
  y = dy;
  return collided;
}

void GraphLayout::bottomUpTraversal( Node* visit_parents_of, int current_depth,
                                     int& min )
{
  int input_count = visit_parents_of->getInputCount();
  NodeInfo* linfo = (NodeInfo*)visit_parents_of->getLayoutInformation();
  int next_depth = current_depth - 1;

  linfo->setGraphDepth( current_depth );
  int input;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !visit_parents_of->isInputVisible( input ) )
      continue;

    List* inputs = (List*)visit_parents_of->getInputArks( input );
    ListIterator iter( *inputs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      int output;
      Node* source = arc->getSourceNode( output );
      NodeInfo* sinfo = (NodeInfo*)source->getLayoutInformation();
      if ( next_depth < min )
        min = next_depth;
      int cd;
      if ( !sinfo )
      {
        sinfo = new NodeInfo();
        sinfo->initialize( source, next_depth );
        cd = next_depth;
      }
      else
      {
        cd = sinfo->getGraphDepth();
      }
      if ( next_depth < cd )
      {
        sinfo->setGraphDepth( next_depth );
        this->bottomUpTraversal( source, next_depth, min );
      }
      else
      {
        this->bottomUpTraversal( source, cd, min );
      }
    }
  }
}

//
// For any node that has an immediate ancestor with a hop count that
// is more than 1 away, we'll try to decrease the hop count so that the
// 2 nodes are adjacent.  This is necessary because we numbered the
// graph starting at the bottom.  We look only at leaf nodes.
// We also examine siblings of the node because that prevents us from
// increasing arc length between our ancestor and our sibling.
//
boolean GraphLayout::adjustHopCounts( Node* reflow[], int reflow_count,
                                      int& min )
{
  int i;
  boolean changes_made = FALSE;
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    if ( this->hasConnectedOutputs( n ) )
      continue;
    NodeInfo* linfo = (NodeInfo*)n->getLayoutInformation();
    int required_hops = this->computeRequiredHopsTo( n );
    int sibling_hops = this->computeRequiredHopsToSiblingsOf( n );
    required_hops = MAX( required_hops, sibling_hops );
    if ( required_hops < linfo->getGraphDepth() )
    {
      int gd = required_hops;
      this->adjustAncestorHops( n, gd - 1, min );
      linfo->setGraphDepth( gd );
      if ( gd < min )
        min = gd;
      changes_made = TRUE;
    }
  }

  return changes_made;
}

void GraphLayout::adjustAncestorHops( Node* parent, int new_hop_count,
                                      int& min )
{
  int input_count = parent->getInputCount();
  int output;
  int input;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !parent->isInputVisible( input ) )
      continue;
    List* arcs = (List*)parent->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* source = arc->getSourceNode( output );
      NodeInfo* linfo = (NodeInfo*)source->getLayoutInformation();
      if ( new_hop_count < linfo->getGraphDepth() )
      {
        linfo->setGraphDepth( new_hop_count );
        if ( new_hop_count < min )
          min = new_hop_count;
        this->adjustAncestorHops( source, new_hop_count - 1, min );
      }
    }
  }
}

//
// When we decrement a node's hop count, we also want to decrement any
// descendants of the node if the descendant has no other inputs and
// no outputs.
//
void GraphLayout::adjustDescendantHops( Node* parent, int new_hop_count )
{
  int output_count = parent->getOutputCount();
  int output;
  int input;
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !parent->isOutputVisible( output ) )
      continue;
    List* arcs = (List*)parent->getOutputArks( output );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* dest = arc->getDestinationNode( input );
      boolean dummy;
      if ( GraphLayout::IsSingleInputNoOutputNode( dest, dummy, FALSE ) )
      {
        NodeInfo* info = (NodeInfo*)dest->getLayoutInformation();
        ASSERT( new_hop_count <= info->getGraphDepth() );
#if defined( DEBUG_PLACEMENT )
        if ( debug )
        {
          fprintf( stdout, "%s[%d] moving %s:%d from %d to %d\n", __FILE__,
                   __LINE__, dest->getNameString(), dest->getInstanceNumber(),
                   info->getGraphDepth(), new_hop_count );
        }
#endif
        info->setGraphDepth( new_hop_count );
      }
    }
  }
}

int GraphLayout::computeRequiredHopsTo( Node* n )
{
  int output;
  int max_count = 1;
  int input_count = n->getInputCount();
  int input;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* arcs = (List*)n->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      int count = this->computeRequiredHopsTo( arc->getSourceNode( output ) );
      max_count = MAX( count + 1, max_count );
    }
  }
  return max_count;
}

int GraphLayout::computeRequiredHopsToSiblingsOf( Node* n )
{
  int dummy;
  int input_count = n->getInputCount();
  int max_hop_count = 1;
  int input;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* arcs = (List*)n->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* source = arc->getSourceNode( dummy );

      int output_count = source->getOutputCount();
      // for each output, fetch connected nodes.
      int output;
      for ( output = 1; output <= output_count; output++ )
      {
        if ( !source->isOutputVisible( output ) )
          continue;
        List* oarcs = (List*)source->getOutputArks( output );
        if ( !oarcs )
          continue;
        ListIterator it( *oarcs );
        Ark* oarc;
        // for each of those nodes fetch required hops
        while ( ( oarc = (Ark*)it.getNext() ) )
        {
          Node* dest = oarc->getDestinationNode( dummy );
          max_hop_count =
              MAX( max_hop_count, this->computeRequiredHopsTo( dest ) );
        }
      }
    }
  }
  return max_hop_count;
}

//
// compute hops by starting at every leaf node and walking up the graph.
// Initialize the hop counter with a huge number and decrement by 1 at
// each hop.  Then translate all hop counts so that the smallest is set
// to 1.  Then adjust all hop counters so that there is no unneeded
// distance between connected nodes.  We get unneeded space because
// we default leaf nodes to the largest hop count even though that isn't
// accurate.
//
void GraphLayout::computeHopCounts( Node* reflow[], int reflow_count )
{
  int i;
  //
  // The starting hop counter has no units.  After we finish, we'll
  // translate all hop counters so that the smallest one in the graph
  // is set to 1.
  //
  int smallest_hop_count = 99999;
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    if ( !this->hasConnectedOutputs( n ) )
    {
      NodeInfo* linfo = new NodeInfo();
      linfo->initialize( n, 99999 );
      this->bottomUpTraversal( n, 99999, smallest_hop_count );
    }
  }

  boolean changes_made;

  //
  // We might want to make some adjustments to hop counts.  Sounds like
  // nonsense, but the problem is that there are some nodes that could
  // really have several different hop counts.  Think about a receiver
  // wired directly to an (and only to an) output.  Should the receiver
  // be marked 1 and the output be marked 2?  ...or should the output be
  // (max hops) and the receiver be 1-max?  Usually I've tried to keep
  // things pushed down towards the bottom of the graph.  Here we want
  // to push things back towards the top of the graph i.e. reduce the
  // hop count if that will have the effect of shorting the arcs.
  //
  changes_made = TRUE;
  while ( changes_made )
    changes_made =
        this->adjustHopCounts( reflow, reflow_count, smallest_hop_count );

  //
  // Rules say that we decrement the hop count of any node that is
  // connected to multiple non-consecutive input tabs on 1 row.
  // The idea is to devote more screen realestate to displaying
  // lines if there are lots of lines between 1 pair of nodes.
  //
  do
  {
    changes_made = FALSE;
    for ( i = 0; i < reflow_count; i++ )
    {
      Node* n = reflow[i];
      changes_made |= this->spreadOutSpaghettiFrom( n, smallest_hop_count );
    }
  } while ( changes_made );

  //
  // Before we raise the curtain, just one more tweak.  Sometimes
  // (usually at the top of a graph) we get some nodes that have a slew of
  // recievers providing inputs.  It's difficult to place all of these
  // in a pleasing way, so  we'll do a final check for this.  If the
  // situation exists, then we'll artificially decrement the hop count
  // for every other reciever so that the pattern is a little garbagey
  // looking.  We sort before the call because if obviates the need
  // to make the call in a loop the way we do above.
  //
  qsort( reflow, reflow_count, sizeof( Node* ), NodeInfo::SortByHop );
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    this->fixForTooManyReceivers( n, smallest_hop_count );
  }

  //
  // Translate to the origin
  //
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    NodeInfo* linfo = (NodeInfo*)n->getLayoutInformation();
    ASSERT( linfo );
    int gd = linfo->getGraphDepth();
    gd = ( gd - smallest_hop_count ) + 1;
    linfo->setGraphDepth( gd );
  }
}

//
// if n has multiple arcs that go to the next higher hop count, and those
// arcs aren't consecutive, then decrement n's hop count.  Reasoning is that
// having too many arcs in a cramped area is hard to read.
//
boolean GraphLayout::spreadOutSpaghettiFrom( Node* n, int& min )
{
  int dummy;
  if ( this->countConnectedOutputs( n, 1, dummy ) <= 1 )
    return FALSE;

  // don't screw around with gets and sets
  const char* name = n->getNameString();
  if ( EqualString( name, "GetLocal" ) || EqualString( name, "GetGlobal" ) ||
       EqualString( name, "Get" ) )
  {
    return FALSE;
  }

  boolean retval = FALSE;

  NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
  int depth = info->getGraphDepth();
  int output_count = n->getOutputCount();
  int output;
  Ark* arc;
  int levels_to_decr = 0;
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !n->isOutputVisible( output ) )
      continue;
    List* arcs = (List*)n->getOutputArks( output );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    int input;
    Node* arc_dest = NUL( Node* );
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* dest = arc->getDestinationNode( input );
      NodeInfo* dinfo = (NodeInfo*)dest->getLayoutInformation();
      int cnctn_count = this->countConnectionsBetween( n, dest, FALSE );
      int desired_depth = dinfo->getGraphDepth() - cnctn_count;
      if ( depth > desired_depth )
      {
        levels_to_decr = MAX( levels_to_decr, ( depth - desired_depth ) );
      }
    }
  }

  if ( levels_to_decr )
  {
    int new_depth = depth - levels_to_decr;
#if defined( DEBUG_PLACEMENT )
    if ( debug )
    {
      fprintf( stdout, "%s[%d] changing %s:%d from %d to %d\n", __FILE__,
               __LINE__, n->getNameString(), n->getInstanceNumber(), depth,
               new_depth );
    }
#endif
    this->adjustAncestorHops( n, new_depth - 1, min );
    this->adjustDescendantHops( n, new_depth + 1 );
    if ( new_depth < min )
      min = new_depth;
    info->setGraphDepth( new_depth );
    retval = TRUE;
  }

  return retval;
}

//
// If a node has wide recievers (a.k.a no input-1 output node)
// connected to adjacent input tabs then
// we'll decrement the hop count of 1 receiver so that things aren't
// bunched up too much.  In general this is bad because anything that
// increases arc length is likely to increase the wire crossings.
//
void GraphLayout::fixForTooManyReceivers( Node* n, int& min )
{
  NodeInfo* ninfo = (NodeInfo*)n->getLayoutInformation();
  int dummy;
  int input;
  int input_count = n->getInputCount();
  List wide_nodes;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* arcs = (List*)n->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* source = arc->getSourceNode( dummy );
      if ( wide_nodes.isMember( source ) )
        continue;
      if ( !this->hasNoCloserDescendant( source, n ) )
        continue;
      LayoutInfo* linfo = (LayoutInfo*)source->getLayoutInformation();
      int w, h;
      linfo->getXYSize( w, h );
      wide_nodes.appendElement( source );
    }
  }
  int wnsize = wide_nodes.getSize();
  if ( wnsize <= 2 )
    return;

  // saw tooth pattern
  //  We're controlling how high up/down the pattern goes.
  int state = 0;
  int max_state = wnsize >> 1;
  if ( wnsize & 1 )
    max_state++;
  int incr = 1;
  boolean had_inputs = FALSE;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* arcs = (List*)n->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* source = arc->getSourceNode( dummy );
      if ( state == 3 )
      {
        if ( ( !this->hasConnectedInputs( source ) ) && ( !had_inputs ) )
          state = 0;
      }
      NodeInfo* linfo = (NodeInfo*)source->getLayoutInformation();
      int gd;
      switch ( state )
      {
        case -1:
          incr = -incr;
        case 0:
          state = 1;
          break;
        default:
          gd = ninfo->getGraphDepth() - ( state + 1 );
          // if this actually does anything...
          if ( gd < linfo->getGraphDepth() )
          {
            this->adjustAncestorHops( source, gd - 1, min );
            linfo->setGraphDepth( gd );
            if ( gd < min )
              min = gd;
          }
          state += incr;
          break;
      }
      if ( state == max_state )
      {
        incr = -incr;
        state += 2 * incr;
      }
      had_inputs = this->hasConnectedInputs( source );
    }
  }
}

//
// return TRUE if dest has the hop count that is closest to the hop
// count of source.  return FALSE if there is some other node that's connected
// to source that has a shorter arcs.  We use this information in order to
// cause source to be placed with its closest living relative.
// return FALSE if there is some other node that's connected to dest
// by more arks than source.
//
boolean GraphLayout::hasNoCloserDescendant( Node* source, Node* dest )
{
  int dummy;
  int output;
  NodeInfo* src_info = (NodeInfo*)source->getLayoutInformation();
  NodeInfo* dst_info = (NodeInfo*)dest->getLayoutInformation();

  int connection_count_to_beat = this->countConnectionsBetween( source, dest );

  int min_depth = dst_info->getGraphDepth();
  int output_count = source->getOutputCount();
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !source->isOutputVisible( output ) )
      continue;
    List* arcs = (List*)source->getOutputArks( output );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* destination = arc->getDestinationNode( dummy );
      if ( destination == dest )
        continue;
      NodeInfo* info = (NodeInfo*)destination->getLayoutInformation();
      if ( this->countConnectionsBetween( source, destination ) <
           connection_count_to_beat )
      {
        continue;
      }
      if ( info->getGraphDepth() < min_depth )
      {
        // a closer relative was found
        return FALSE;
      }
    }
  }

  return TRUE;
}

//
// Compute the location of the new placements relative to the old
// placements and adjust the new placements' locations so that the
// 2 bounding boxes don't intersect.
// If known_disjoint is TRUE, then that means we can move the new set
// anywhere we want it.  Otherwise we have to maintain any left-of
// right-of relationships.
//
void GraphLayout::repositionNewPlacements( Node* root, boolean disjoint,
                                           List& placed )
{
  Node* n;
  NodeInfo* ninfo = (NodeInfo*)root->getLayoutInformation();
  LayoutGroup* group = ninfo->getLayoutGroup();
  placed.appendElement( root );

#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    ListIterator li( placed );
    Node* node;
    fprintf( stdout, "%s[%d] placing in group %d...\n", __FILE__, __LINE__,
             group->getId() );
    while ( node = (Node*)li.getNext() )
    {
      fprintf( stdout, "\t%s:%d\n", node->getNameString(),
               node->getInstanceNumber() );
    }
  }
#endif

  int minx2, miny2, maxx2, maxy2;
  this->computeBoundingBox( placed, minx2, miny2, maxx2, maxy2 );

  boolean group_had_placements = TRUE;
  int minx1, miny1, maxx1, maxy1;

  //
  // At this point n is not initialized but the method only reads from
  // n if the connected list hasn't been built yet.  At this point,
  // all such lists are built, so the uninitialized n is supplied here
  // only as a misfeature of the api.
  //
  List* connected = ninfo->getConnectedNodes( n );

  if ( !disjoint )
  {
    // Form the bounding box of the starting condition
    List original;
    Node* node;
    ListIterator iter( *connected );
    while ( ( node = (Node*)iter.getNext() ) )
    {
      LayoutInfo* info = (LayoutInfo*)node->getLayoutInformation();
      if ( info->isPositioned() )
      {
        if ( !placed.isMember( node ) )
          original.appendElement( node );
      }
    }
    group_had_placements =
        this->computeBoundingBox( original, minx1, miny1, maxx1, maxy1 );
  }

  int ydelta, xdelta;
  if ( ( disjoint ) || ( !group_had_placements ) )
  {
    xdelta = -minx2;
    ydelta = -miny2;
    ListIterator iter( placed );
    while ( ( n = (Node*)iter.getNext() ) )
    {
      NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
      int x, y;
      info->getXYPosition( x, y );
      info->setProposedLocation( x + xdelta, y + ydelta );
    }
    group->initialize( &placed );
    return;
  }

  ASSERT( group_had_placements );
  //
  // Now we have 2 bounding boxes, 1 for the nodes that were
  // already placed and 1 for the batch of additional placements.
  // We know we can scoot the new comers over so that the 2 bounding
  // boxes butt up against each other, but we might be able to do
  // better.  How to figure out how much we can scoot over without
  // having overlapping?
  //
  // The goal is to scoot over far enough so that a wire that joins
  // 2 nodes - 1 in the new placments and 1 in the old placements -
  // becomes a straight line.
  //
  // Collect all the arcs that cross from 1 set to the other set.
  // Then sort those arcs by decreasing length.  Then for each
  // arc, try to line things up without any collisions.  If none
  // works, then just butt the bounding boxes up against eachother.
  //
  List crossing_arcs;
  ListIterator iter( placed );
  while ( ( n = (Node*)iter.getNext() ) )
  {
    int input_count = n->getInputCount();
    int output_count = n->getOutputCount();
    int input, output;
    for ( input = 1; input <= input_count; input++ )
    {
      if ( !n->isInputVisible( input ) )
        continue;
      List* arks = (List*)n->getInputArks( input );
      if ( !arks )
        continue;
      ListIterator li( *arks );
      Ark* arc;
      while ( ( arc = (Ark*)li.getNext() ) )
      {
        Node* source = arc->getSourceNode( output );
        NodeInfo* sinfo = (NodeInfo*)source->getLayoutInformation();
        if ( !sinfo->isPositioned() )
          continue;
        if ( !placed.isMember( source ) )
        {
          if ( crossing_arcs.isMember( arc ) == FALSE )
            crossing_arcs.appendElement( arc );
        }
      }
    }
    for ( output = 1; output <= output_count; output++ )
    {
      if ( !n->isOutputVisible( output ) )
        continue;
      List* arks = (List*)n->getOutputArks( output );
      if ( !arks )
        continue;
      ListIterator li( *arks );
      Ark* arc;
      while ( ( arc = (Ark*)li.getNext() ) )
      {
        Node* dest = arc->getDestinationNode( input );
        NodeInfo* dinfo = (NodeInfo*)dest->getLayoutInformation();
        if ( !dinfo->isPositioned() )
          continue;
        if ( !placed.isMember( dest ) )
        {
          if ( crossing_arcs.isMember( arc ) == FALSE )
            crossing_arcs.appendElement( arc );
        }
      }
    }
  }
  int maxarcs = 128;
  int arc_count = crossing_arcs.getSize();
  arc_count = MIN( maxarcs, arc_count );
  // this assert says that we should have detected a disconnected
  // subgraph in an earlier test.
  // ASSERT(arc_count);
  // arc_count can be 0 if we the nodes to which the new placements
  // are connected haven't been placed yet.

  boolean prefer_left = TRUE;

  boolean arc_found = FALSE;
  Ark* aa[128];
  int i, j;
  if ( arc_count )
  {
    for ( i = 0, j = 1; i < arc_count; i++, j++ )
    {
      aa[i] = (Ark*)crossing_arcs.getElement( j );
    }
    qsort( aa, arc_count, sizeof( Ark* ), GraphLayout::ArcComparator );

    //
    // There may come a time when we have to decide if we want to place
    // new nodes to the left or to the right of existing placements.  When
    // we use this info we're really just taking our chances.  Also, we don't
    // always need this info but we have to have it computed before we need
    // it.
    int center = 0;
    int j;
    for ( j = 0; j < arc_count; j++ )
    {
      //
      // The choice of arc has an influence of the way we lay out the
      // graph especially when Gets and Sets are involved.  I don't
      // know of a 'proper' way to pick one arc. So, loop over all arcs
      // involved, give each 1 vote which it can cast in 1 of 3 ways...
      // go left, go right, don't care.
      //
      boolean prefer_left = FALSE;
      Ark* arc = aa[j];

      int input, output;
      Node* src = arc->getSourceNode( output );
      Node* dst = arc->getDestinationNode( input );
      int nth_input_tab, nth_output_tab;
      int vi = this->countConnectedInputs( dst, input, nth_input_tab );
      // destination node casts his vote...
      if ( ( vi == 1 ) ||
           ( ( nth_input_tab == ( vi >> 1 ) ) && ( ( vi & 1 ) == 1 ) ) )
      {
// don't care
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s destination didn't vote\n",
                   dst->getNameString() );
#endif
      }
      else if ( nth_input_tab <= ( vi >> 1 ) )
      {
        prefer_left = ( placed.isMember( dst ) == FALSE );
        center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s destination voted %s\n", dst->getNameString(),
                   ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
      }
      else if ( nth_input_tab > ( vi >> 1 ) )
      {
        prefer_left = placed.isMember( dst );
        center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s destination voted %s\n", dst->getNameString(),
                   ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
      }

      // source node casts his vote..
      int vo = this->countConnectedOutputs( src, output, nth_output_tab );
      if ( ( vo == 1 ) ||
           ( ( nth_output_tab == ( vo >> 1 ) ) && ( ( vo & 1 ) == 1 ) ) )
      {
// don't care
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s source didn't vote\n", src->getNameString() );
#endif
      }
      else if ( nth_output_tab <= ( vo >> 1 ) )
      {
        prefer_left = ( placed.isMember( src ) == FALSE );
        center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s source voted %s\n", src->getNameString(),
                   ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
      }
      else if ( nth_output_tab > ( vo >> 1 ) )
      {
        prefer_left = placed.isMember( src );
        center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
        if ( debug )
          fprintf( stdout, "\t%s source voted %s\n", src->getNameString(),
                   ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
      }

      // the source may have another node connected to the same output.
      // It should cast a vote also.
      List* arcs = (List*)src->getOutputArks( output );
      ListIterator iter( *arcs );
      Node* other_dst = NUL( Node* );
      int oinput;
      while ( ( arc = (Ark*)iter.getNext() ) )
      {
        other_dst = arc->getDestinationNode( oinput );
        if ( other_dst == dst )
          continue;
        if ( placed.isMember( other_dst ) )
          continue;
        break;
      }
      if ( other_dst )
      {
        int vi = this->countConnectedInputs( other_dst, oinput, nth_input_tab );
        if ( vi == 1 )
        {
// don't care
#if defined( DEBUG_PLACEMENT )
          if ( debug )
            fprintf( stdout, "\t%s destination didn't vote\n",
                     dst->getNameString() );
#endif
        }
        else if ( nth_input_tab <= ( vi >> 1 ) )
        {
          prefer_left = TRUE;
          center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
          if ( debug )
            fprintf( stdout, "\t%s source voted %s\n", src->getNameString(),
                     ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
        }
        else if ( nth_input_tab > ( vi >> 1 ) )
        {
          prefer_left = FALSE;
          center += ( prefer_left ? -1 : 1 );
#if defined( DEBUG_PLACEMENT )
          if ( debug )
            fprintf( stdout, "\t%s source voted %s\n", src->getNameString(),
                     ( prefer_left ? "LEFT" : "RIGHT" ) );
#endif
        }
      }
    }
    prefer_left = ( center <= 0 );

    // for each arc, compute the x location that will make the wire
    // straight and test each node in placed to see if the entire
    // set can move.
    for ( i = 0; i < arc_count; i++ )
    {
      Ark* arc = aa[i];
      int input, output;
      Node* source = arc->getSourceNode( output );
      Node* dest = arc->getDestinationNode( input );
      NodeInfo* sinfo = (NodeInfo*)source->getLayoutInformation();
      NodeInfo* dinfo = (NodeInfo*)dest->getLayoutInformation();
      boolean node_can_move = FALSE;
      int prevx, prevy;

      int x, y, dummy;
      if ( placed.isMember( source ) )
      {
        if ( !this->positionSourceOverDest( arc, x, y ) )
        {
          node_can_move = TRUE;
          sinfo->getXYPosition( prevx, prevy );
          xdelta = x - prevx;
          ydelta = y - prevy;
        }
      }
      else
      {
        if ( !this->positionDestUnderSource( arc, x, y ) )
        {
          node_can_move = TRUE;
          dinfo->getXYPosition( prevx, prevy );
          xdelta = x - prevx;
          ydelta = y - prevy;
        }
        else if ( !this->positionDestBesideSibling( arc, x, y, prefer_left,
                                                    &placed ) )
        {
          // potential problem.  I'm not checking that the arc isn't
          // shorter than some other arc that the destination node
          // has coming in.  If it is shorter, then I could place
          // a destination node higher on the screen that it ought
          // to be.  An example of this in InterpolateCameraMacro.net.
          node_can_move = TRUE;
          dinfo->getXYPosition( prevx, prevy );
          xdelta = x - prevx;
          ydelta = y - prevy;
        }
      }

      // now check all other nodes.
      if ( node_can_move )
      {
        arc_found = TRUE;
        // ListIterator iter(*connected);
        ListIterator iter( placed );
        Node* n;
        while ( ( n = (Node*)iter.getNext() ) )
        {
          NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
          int nx, ny;
          info->getXYPosition( nx, ny );
          if ( !this->nodeCanMoveTo( n, nx + xdelta, ny + ydelta ) )
          {
            arc_found = FALSE;
            break;
          }
        }
        if ( arc_found )
          break;
      }
    }
  }

  // If no arc is found, then compute the xdelta so that the
  // two bounding boxes butt up against eachother.  The only
  // missing information is which bounding box should be on
  // the left and which on the right.  This is difficult to
  // figure out.  Possible clues are the positioning of the
  // input and output tabs in use.  A high-numbered input
  // wants to be on the left of its source.  A low-numbered
  // output wants to be on the right of its destination.
  if ( !arc_found )
  {
#if defined( DEBUG_PLACEMENT )
    if ( debug )
      fprintf( stdout, "%s[%d] %d arcs will vote on placement\n", __FILE__,
               __LINE__, arc_count );
#endif

    if ( prefer_left )
    {
      xdelta = -( maxx2 + GraphLayout::NodeSpacing - minx1 );
      ydelta = 0;
    }
    else
    {
      xdelta = ( maxx1 + GraphLayout::NodeSpacing - minx2 );
      ydelta = 0;
    }
  }

  //
  // perform the translation
  //
  iter.setList( placed );
  while ( ( n = (Node*)iter.getNext() ) )
  {
    NodeInfo* linfo = (NodeInfo*)n->getLayoutInformation();
    int x, y;
    ASSERT( linfo->isPositioned() );
    linfo->getXYPosition( x, y );
#if defined( DEBUG_PLACEMENT )
    if ( debug )
      fprintf( stdout, "%s[%d] moving %s from %d,%d to %d,%d\n", __FILE__,
               __LINE__, n->getNameString(), x, y, x + xdelta, y + ydelta );
#endif
    linfo->setProposedLocation( x + xdelta, y + ydelta );
  }
  group->initialize( &placed );
}

void GraphLayout::prepareAnnotationPlacement( List& decorators, Node* reflow[],
                                              int reflow_count,
                                              const List& all_decorators,
                                              WorkSpace* workSpace, int& widest,
                                              int& tallest )
{
  //
  // exclude the nodes that aren't in the current page
  //
  ListIterator decs;
  VPEAnnotator* dec;
  decs.setList( (List&)all_decorators );
  while ( ( dec = (VPEAnnotator*)decs.getNext() ) )
  {
    if ( dec->getWorkSpace() != workSpace )
      continue;
    decorators.appendElement( dec );
    AnnotationInfo* ai = new AnnotationInfo();
    ai->initialize( dec );
    ai->findNearestNode( reflow, reflow_count );

    int w, h;
    ai->getXYSize( w, h );
    NodeDistance* nd = ai->nearby[0];
    if ( nd->getLocation() & DECORATOR_LEFT )
    {
      if ( w > widest )
        widest = w;
    }
    if ( nd->getLocation() & DECORATOR_ABOVE )
    {
      if ( h > tallest )
        tallest = h;
    }
  }
}

AnnotationInfo::~AnnotationInfo()
{
  if ( this->nearby )
  {
    int i;
    for ( i = 0; i < this->nearbyCnt; i++ )
      delete this->nearby[i];
    free( this->nearby );
  }
}
//
// Distance between 2 rectangles is the vertical distance between 2 horizontal
// line segments or horizontal distance between 2 vertical line segments
// if they overlap.  If the line segments don't overlap, then the distance
// is the smallest of the 4 distances between the the endpoints of the line
// segments.
//
void AnnotationInfo::findNearestNode( Node* reflow[], int reflow_count )
{
  int i;
  ASSERT( this->isInitialized() );

  int x1 = this->orig_x;
  int x2 = this->orig_x + ( this->w - 1 );
  int y1 = this->orig_y;
  int y2 = this->orig_y + ( this->h - 1 );

  this->nearby =
      (NodeDistance**)malloc( sizeof( NodeDistance* ) * reflow_count );
  ;
  this->nearbyCnt = reflow_count;

  int min_dist = 999999;
  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    LayoutInfo* linfo = (LayoutInfo*)n->getLayoutInformation();
    int nx1, ny1, nw, nh;
    linfo->getOriginalXYPosition( nx1, ny1 );
    linfo->getXYSize( nw, nh );
    int nx2 = nx1 + ( nw - 1 );
    int ny2 = ny1 + ( nh - 1 );

    int vdist = 999999;
    int hdist = 999999;

    // vertical edges
    int hloc = 0;
    if ( x1 > nx2 )
    {
      hloc = DECORATOR_RIGHT;
      if ( ( y1 >= ny1 ) && ( y1 <= ny2 ) )
      {
        hdist = x1 - nx2;
      }
      else if ( ( y2 >= ny1 ) && ( y2 <= ny2 ) )
      {
        hdist = x1 - nx2;
      }
      else if ( ( y1 <= ny1 ) && ( y2 >= ny2 ) )
      {
        hdist = x1 - nx2;
      }
      else if ( y1 > ny2 )
      {
        hdist = (int)sqrt( (double)( ( x1 - nx2 ) * ( x1 - nx2 ) +
                                     ( y1 - ny2 ) * ( y1 - ny2 ) ) );
        hloc |= DECORATOR_BELOW;
      }
      else
      {
        hdist = (int)sqrt( (double)( ( x1 - nx2 ) * ( x1 - nx2 ) +
                                     ( y2 - ny1 ) * ( y2 - ny1 ) ) );
        hloc |= DECORATOR_ABOVE;
      }
    }
    else if ( x2 < nx1 )
    {
      hloc = DECORATOR_LEFT;
      if ( ( y1 >= ny1 ) && ( y1 <= ny2 ) )
      {
        hdist = nx1 - x2;
      }
      else if ( ( y2 >= ny1 ) && ( y2 <= ny2 ) )
      {
        hdist = nx1 - x2;
      }
      else if ( ( y1 <= ny1 ) && ( y2 >= ny2 ) )
      {
        hdist = nx1 - x2;
      }
      else if ( y1 > ny2 )
      {
        hdist = (int)sqrt( (double)( ( x2 - nx1 ) * ( x2 - nx1 ) +
                                     ( y1 - ny2 ) * ( y1 - ny2 ) ) );
        hloc |= DECORATOR_BELOW;
      }
      else
      {
        hdist = (int)sqrt( (double)( ( x2 - nx1 ) * ( x2 - nx1 ) +
                                     ( y2 - ny1 ) * ( y2 - ny1 ) ) );
        hloc |= DECORATOR_ABOVE;
      }
    }

    // horizontal edges
    int vloc = 0;
    if ( y1 > ny2 )
    {
      vloc = DECORATOR_BELOW;
      if ( ( x1 >= nx1 ) && ( x1 <= nx2 ) )
      {
        vdist = y1 - ny2;
      }
      else if ( ( x2 >= nx1 ) && ( x2 <= nx2 ) )
      {
        vdist = y1 - ny2;
      }
      else if ( ( x1 <= nx1 ) && ( x2 >= nx2 ) )
      {
        vdist = y1 - ny2;
      }
      else if ( x1 > nx2 )
      {
        vdist = (int)sqrt( (double)( ( x1 - nx2 ) * ( x1 - nx2 ) +
                                     ( y1 - ny2 ) * ( y1 - ny2 ) ) );
        vloc |= DECORATOR_RIGHT;
      }
      else
      {
        vdist = (int)sqrt( (double)( ( x2 - nx1 ) * ( x2 - nx1 ) +
                                     ( y1 - ny2 ) * ( y1 - ny2 ) ) );
        vloc |= DECORATOR_LEFT;
      }
    }
    else if ( y2 < ny1 )
    {
      vloc = DECORATOR_ABOVE;
      if ( ( x1 >= nx1 ) && ( x1 <= nx2 ) )
      {
        vdist = ny1 - y2;
      }
      else if ( ( x2 >= nx1 ) && ( x2 <= nx2 ) )
      {
        vdist = ny1 - y2;
      }
      else if ( ( x1 <= nx1 ) && ( x2 >= nx2 ) )
      {
        vdist = ny1 - y2;
      }
      else if ( x1 > nx2 )
      {
        vdist = (int)sqrt( (double)( ( x1 - nx2 ) * ( x1 - nx2 ) +
                                     ( y2 - ny1 ) * ( y2 - ny1 ) ) );
        vloc |= DECORATOR_RIGHT;
      }
      else
      {
        vdist = (int)sqrt( (double)( ( x2 - nx1 ) * ( x2 - nx1 ) +
                                     ( y2 - ny1 ) * ( y2 - ny1 ) ) );
        vloc |= DECORATOR_LEFT;
      }
    }

    if ( hdist < vdist )
      this->nearby[i] = new NodeDistance( n, hdist, hloc );
    else
      this->nearby[i] = new NodeDistance( n, vdist, vloc );
  }
  qsort( this->nearby, this->nearbyCnt, sizeof( NodeDistance* ),
         AnnotationInfo::SortByDistance );
}

int GraphLayout::ArcComparator( const void* a, const void* b )
{
  Ark** aptr = (Ark**)a;
  Ark** bptr = (Ark**)b;
  Ark* aarc = *aptr;
  Ark* barc = *bptr;

  int ahops, bhops;
  Node* src, *dst;
  int dummy;

  src = aarc->getSourceNode( dummy );
  dst = aarc->getDestinationNode( dummy );
  NodeInfo* sinfo = (NodeInfo*)src->getLayoutInformation();
  NodeInfo* dinfo = (NodeInfo*)dst->getLayoutInformation();
  ahops = dinfo->getGraphDepth() - sinfo->getGraphDepth();

  src = barc->getSourceNode( dummy );
  dst = barc->getDestinationNode( dummy );
  sinfo = (NodeInfo*)src->getLayoutInformation();
  dinfo = (NodeInfo*)dst->getLayoutInformation();
  bhops = dinfo->getGraphDepth() - sinfo->getGraphDepth();

  if ( ahops < bhops )
    return -1;
  if ( ahops > bhops )
    return -1;
  return 0;
}

int AnnotationInfo::SortByDistance( const void* a, const void* b )
{
  NodeDistance** aptr = (NodeDistance**)a;
  NodeDistance** bptr = (NodeDistance**)b;
  NodeDistance* aNd = (NodeDistance*)*aptr;
  NodeDistance* bNd = (NodeDistance*)*bptr;
  if ( aNd->getDistance() < bNd->getDistance() )
    return -1;
  if ( aNd->getDistance() > bNd->getDistance() )
    return 1;
  return 0;
}

int AnnotationInfo::NextX;
int AnnotationInfo::NextY;

void AnnotationInfo::reposition( Node* reflow[], int reflow_count,
                                 List& others )
{
  // spot sequence
  int spots[] = {
      DECORATOR_RIGHT,                   DECORATOR_RIGHT | DECORATOR_ABOVE,
      DECORATOR_RIGHT | DECORATOR_BELOW, DECORATOR_LEFT,
      DECORATOR_LEFT | DECORATOR_ABOVE,  DECORATOR_LEFT | DECORATOR_BELOW,
      DECORATOR_ABOVE,                   DECORATOR_BELOW};
  int spot_cnt = sizeof( spots ) / sizeof( int );

  boolean did_it = FALSE;

  int node_to_try = 0;
  while ( ( !did_it ) && ( node_to_try < this->nearbyCnt ) )
  {

    NodeDistance* nd = this->nearby[node_to_try];
    Node* n = nd->getNode();
    int loc = nd->getLocation();
    LayoutInfo* linfo = (LayoutInfo*)n->getLayoutInformation();
    int nodex, nodey;
    int nodew, nodeh;
    linfo->getXYPosition( nodex, nodey );
    linfo->getXYSize( nodew, nodeh );

    int spot_index = 0;
    while ( spots[spot_index] != loc )
      spot_index++;

    int tries = 0;
    while ( tries < spot_cnt )
    {
      int location = spots[spot_index];
      int x = nodex + ( ( nodew - this->w ) / 2 );
      int y = nodey + ( ( nodeh - this->h ) / 2 );
      if ( location & DECORATOR_ABOVE )
      {
        y = nodey - ( 1 + this->h );
      }
      else if ( location & DECORATOR_BELOW )
      {
        y = nodey + nodeh + 1;
      }
      if ( location & DECORATOR_LEFT )
      {
        x = nodex - ( 1 + this->w );
      }
      else if ( location & DECORATOR_RIGHT )
      {
        x = nodex + 1 + nodew;
      }

      if ( ( x > 0 ) && ( y > 0 ) &&
           ( GraphLayout::CanMoveTo( this, x, y, reflow, reflow_count,
                                     &others ) ) )
      {
        this->setProposedLocation( x, y );
        did_it = TRUE;
        break;
      }
      tries++;
      spot_index++;
      if ( spot_index == spot_cnt )
        spot_index = 0;
    }
    node_to_try++;
  }

  if ( !did_it )
  {
    this->setProposedLocation( AnnotationInfo::NextX, AnnotationInfo::NextY );
    AnnotationInfo::NextY += this->h + 1;
  }
}

void LayoutGroup::initialize( List* nodes )
{
  ListIterator iter( *nodes );
  Node* n;
  while ( ( n = (Node*)iter.getNext() ) )
  {
    NodeInfo* linfo = (NodeInfo*)n->getLayoutInformation();
    int x, y, w, h;
    linfo->getOriginalXYPosition( x, y );
    linfo->getXYSize( w, h );
    if ( x < this->orig_x1 )
      this->orig_x1 = x;
    if ( y < this->orig_y1 )
      this->orig_y1 = y;
    if ( ( x + w ) > this->orig_x2 )
      this->orig_x2 = x + w;
    if ( ( y + h ) > this->orig_y2 )
      this->orig_y2 = y + h;
    linfo->getXYPosition( x, y );
    if ( x < this->x1 )
      this->x1 = x;
    if ( y < this->y1 )
      this->y1 = y;
    if ( ( x + w ) > this->x2 )
      this->x2 = x + w;
    if ( ( y + h ) > this->y2 )
      this->y2 = y + h;
    linfo->setLayoutGroup( this );
  }
  this->initialized = TRUE;
}

int LayoutGroup::Comparator( const void* a, const void* b )
{
  LayoutGroup** aptr = (LayoutGroup**)a;
  LayoutGroup** bptr = (LayoutGroup**)b;
  LayoutGroup* agroup = *aptr;
  LayoutGroup* bgroup = *bptr;

  //
  // If  the height ranges don't overlap then return the one with
  // the lower y.
  //
  if ( ( agroup->orig_y1 < bgroup->orig_y1 ) &&
       ( agroup->orig_y2 < bgroup->orig_y2 ) )
    return -1;
  if ( ( bgroup->orig_y1 < agroup->orig_y1 ) &&
       ( bgroup->orig_y2 < agroup->orig_y2 ) )
    return 1;

  //
  // If the height ranges overlap, then return the one with the
  // large x.
  //
  if ( ( agroup->orig_x1 < bgroup->orig_x1 ) &&
       ( agroup->orig_x2 < bgroup->orig_x2 ) )
    return -1;
  if ( ( bgroup->orig_x1 < agroup->orig_x1 ) &&
       ( bgroup->orig_x2 < agroup->orig_x2 ) )
    return 1;

  if ( ( ( agroup->orig_y1 + agroup->orig_y2 ) >> 1 ) <
       ( ( bgroup->orig_y1 + bgroup->orig_y2 ) >> 1 ) )
    return -1;
  if ( ( ( agroup->orig_y1 + agroup->orig_y2 ) >> 1 ) >
       ( ( bgroup->orig_y1 + bgroup->orig_y2 ) >> 1 ) )
    return 1;
  if ( ( ( agroup->orig_x1 + agroup->orig_x2 ) >> 1 ) <
       ( ( bgroup->orig_x1 + bgroup->orig_x2 ) >> 1 ) )
    return -1;
  if ( ( ( agroup->orig_x1 + agroup->orig_x2 ) >> 1 ) >
       ( ( bgroup->orig_x1 + bgroup->orig_x2 ) >> 1 ) )
    return 1;
  return 0;
}

void GraphLayout::repositionGroups( Node* reflow[], int reflow_count )
{
  int i;
  LayoutGroup** groups = (LayoutGroup**)malloc( sizeof( LayoutGroup* ) *
                                                this->layout_groups.getSize() );
  ListIterator gi( this->layout_groups );
  LayoutGroup* group;
  int gcnt = 0;
  while ( ( group = (LayoutGroup*)gi.getNext() ) )
    groups[gcnt++] = group;
  qsort( groups, gcnt, sizeof( LayoutGroup* ), LayoutGroup::Comparator );
  int gx = 0, gy = 0;
  int prevy2 = 0;
  int dummy;
  int w = 0, h = 0;
  int max_height_in_line = 0;

  groups[0]->getOriginalXYPosition( dummy, prevy2 );
  groups[0]->getOriginalXYSize( dummy, h );
  prevy2 += h;

  w = h = 0;
  boolean isNewLine = FALSE;
  for ( i = 0; i < gcnt; i++ )
  {
    group = groups[i];
    int x1, y1;
    int ow, oh;
    group->getOriginalXYPosition( x1, y1 );
    group->getOriginalXYSize( ow, oh );
    int w, h;
    group->getXYSize( w, h );
    isNewLine = ( y1 > prevy2 );
    if ( isNewLine )
    {
      gx = 0;
      gy += max_height_in_line + GraphLayout::HeightPerLevel;
      max_height_in_line = h;
    }
    else if ( h > max_height_in_line )
    {
      max_height_in_line = h;
    }
    group->setProposedLocation( gx, gy );
    // printf ("%s[%d] group %d at %d,%d\n", __FILE__,__LINE__,group->getId(),
    // gx, gy);
    gx += w + GraphLayout::GroupSpacing;
    prevy2 = y1 + oh;
  }

  for ( i = 0; i < reflow_count; i++ )
  {
    Node* n = reflow[i];
    NodeInfo* ninfo = (NodeInfo*)n->getLayoutInformation();
    LayoutGroup* group = ninfo->getLayoutGroup();
    int x, y;
    group->getProposedLocation( x, y );
    int x1, y1;
    group->getXYPosition( x1, y1 );
    int nx, ny;
    ninfo->getXYPosition( nx, ny );
    ninfo->setProposedLocation( nx + x - x1, ny + y - y1 );
  }
  free( groups );
}

NodeInfo::~NodeInfo()
{
  if ( this->connected_nodes )
  {
    if ( this->owns_list )
      delete this->connected_nodes;
  }
}

void NodeInfo::setConnectedNodes( List* list )
{
  if ( this->owns_list )
    return;
  this->connected_nodes = list;
}
List* NodeInfo::getConnectedNodes( Node* n )
{
  if ( this->connected_nodes )
    return this->connected_nodes;

  this->connected_nodes = new List();
  this->owns_list = TRUE;
  NodeInfo::BuildList( n, this->connected_nodes );
  return this->connected_nodes;
}

void NodeInfo::BuildList( Node* n, List* nodes )
{
  if ( nodes->isMember( n ) )
    return;
  nodes->appendElement( n );

  NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
  if ( info )
    info->setConnectedNodes( nodes );

  int input_count = n->getInputCount();
  int input;
  int dummy;
  for ( input = 1; input <= input_count; input++ )
  {
    if ( !n->isInputVisible( input ) )
      continue;
    List* arcs = (List*)n->getInputArks( input );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* source = arc->getSourceNode( dummy );
      NodeInfo::BuildList( source, nodes );
    }
  }
  int output_count = n->getOutputCount();
  int output;
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !n->isOutputVisible( output ) )
      continue;
    List* arcs = (List*)n->getOutputArks( output );
    if ( !arcs )
      continue;
    ListIterator iter( *arcs );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* destination = arc->getDestinationNode( dummy );
      NodeInfo::BuildList( destination, nodes );
    }
  }
}

int GraphLayout::countConnectedInputs( Node* n, int input, int& nth_tab )
{
  int input_count = n->getInputCount();
  int i, connected = 0;
  nth_tab = 1;
  for ( i = 1; i <= input_count; i++ )
  {
    if ( !n->isInputVisible( i ) )
      continue;
    if ( n->isInputConnected( i ) )
      connected++;
    if ( i < input )
      nth_tab++;
  }
  return connected;
}

int GraphLayout::countConnectedOutputs( Node* n, int output, int& nth_tab )
{
  int output_count = n->getOutputCount();
  int i, connected = 0;
  nth_tab = 1;
  for ( i = 1; i <= output_count; i++ )
  {
    if ( !n->isOutputVisible( i ) )
      continue;
    if ( n->isOutputConnected( i ) )
      connected++;
    if ( i < output )
      nth_tab++;
  }
  return connected;
}

//
// 0) Decrement the hop count of any node that is connected to multiple
//    non-consecutive input tabs on 1 row.
// 1) Divide all nodes into rows.
// 2) Sort the contents of each row by increasing x coord of the destination.
// 3) Starting with the middle node in the sorted list, position each
//    above its destination or in the case of node traveling more than 1 hops,
//    above a space between nodes, or place the node directly above its
// destination
//    if that is available.
//
void LayoutGroup::layout( Node* node, GraphLayout* mgr, List& positioned )
{
  positioned.clear();

  //
  // Starting with all nodes in this layout group, form an
  // array that we can sort by hop count.  This will be used
  // to form rows.  A node that is in our group is copied into this
  // array if we're going to place the node on this trip up the
  // graph.  We make this decision based on the node's connectivity
  // (and in rare cases by type i.e. Get/Set)  We won't place a node
  // on this trip if the node ought to be placed during some other
  // trip up the graph.  I.O.W. if the node has a closer descendant,
  // then let that descendant take care of placing the node so that
  // the node will be placed in close proximity to the nearby
  // relative instead of close proximity to the distant relative.
  //
  List one_hop_up_nodes;
  List one_hop_up;
  mgr->getSpecialAncestorsOf( node, one_hop_up_nodes, one_hop_up );
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    fprintf( stdout, "%s[%d] Placing ancestors of %s:%d\n", __FILE__, __LINE__,
             node->getNameString(), node->getInstanceNumber() );
    ListIterator li( one_hop_up_nodes );
    Node* n;
    while ( n = (Node*)li.getNext() )
    {
      fprintf( stdout, "\t%s:%d\n", n->getNameString(),
               n->getInstanceNumber() );
    }
  }
#endif
  Node** node_array;
  node_array =
      (Node**)malloc( ( 1 + one_hop_up_nodes.getSize() ) * sizeof( Node* ) );
  int i = 1;
  int nodes = 0;
  int size = one_hop_up_nodes.getSize();
  ASSERT( one_hop_up_nodes.getSize() == one_hop_up.getSize() );
  while ( i <= size )
  {
    Node* n = (Node*)one_hop_up_nodes.getElement( i );
    node_array[nodes++] = n;
    positioned.appendElement( n );
    NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
    info->setDestination( (Ark*)one_hop_up.getElement( i ) );
    i++;
  }
  // at this point nodes  may or may not be equal to ->getSize()
  // add our param manually because it's not one hop up.
  node_array[nodes++] = node;
  qsort( node_array, nodes, sizeof( Node* ), LayoutGroup::SortByHop );

  //
  // Create one data structure for each row in the array.
  // nodes is the wrong number to use here, but rows is guaranteed to
  // be <= nodes
  LayoutRow** row_array = (LayoutRow**)malloc( sizeof( LayoutRow* ) * nodes );
  LayoutRow* row = NUL( LayoutRow* );
  int prev = -1;
  i = 0;
  int rows = 0;
  while ( i < nodes )
  {
    node = node_array[i];
    NodeInfo* ninfo = (NodeInfo*)node->getLayoutInformation();
    if ( ninfo->getGraphDepth() != prev )
    {
      row_array[rows++] = row = new LayoutRow( ninfo->getGraphDepth() );
    }
    row->addNode( node );
    prev = ninfo->getGraphDepth();
    i++;
  }
  int prev_id;
  row_array[0]->sort();
  row_array[0]->layout( mgr, prev_id );
  SlotList* slots = row_array[0]->getSlotList();
  for ( i = 1; i < rows; i++ )
  {
    row_array[i]->sort();
    row_array[i]->layout( slots, mgr, prev_id );
    slots = row_array[i]->getSlotList();
  }

  //
  // provide additional spacing for crowded situations
  //
  this->straightenArcs( row_array, rows );

  for ( i = 0; i < rows; i++ )
    delete row_array[i];
  free( row_array );
  free( node_array );
}

void LayoutRow::sort()
{
  int size = this->nodes.getSize();
  this->node_array = (Node**)malloc( sizeof( Node* ) * size );
  ListIterator iter( this->nodes );
  Node* n;
  int i = 0;
  while ( ( n = (Node*)iter.getNext() ) )
    this->node_array[i++] = n;
  qsort( this->node_array, size, sizeof( Node* ),
         LayoutRow::SortByDestinationX );
  this->sorted_by_destination_x = TRUE;
  this->sorted_by_x = FALSE;
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    fprintf( stdout, "%s[%d] Row %d contains...\n", __FILE__, __LINE__,
             this->getId() );
    int j;
    for ( j = 0; j < size; j++ )
    {
      fprintf( stdout, "\t%s:%d\n", this->node_array[j]->getNameString(),
               this->node_array[j]->getInstanceNumber() );
    }
  }
#endif
}

LayoutRow::~LayoutRow()
{
  if ( this->node_array )
    free( this->node_array );
}

// Among the nodes we're placing, there are no connected outputs.  There
// should be only 1 node in this row.
void LayoutRow::layout( GraphLayout* mgr, int& previous_id )
{
  Node* n = this->node_array[0];
  NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
  if ( !info->isPositioned() )
    info->setProposedLocation( INITIAL_X, INITIAL_Y );
  int x, y, w, h;
  info->getXYSize( w, h );
  info->getXYPosition( x, y );
  int left_edge = x - ( w >> 1 );
  int right_edge = x + ( w >> 1 );
  this->slot_list.clear();
  previous_id = this->getId();
}

SlotList::~SlotList()
{
  ListIterator li( *this );
  Slot* slot;
  while ( ( slot = (Slot*)li.getNext() ) )
    delete slot;
}
//
// Return x if that location is empty.  Otherwise return the next location to
// the left or right that is empty.
//
int SlotList::isAvailable( int x, boolean left )
{
  ListIterator li( *this );
  Slot* slot, *prev = NUL( Slot* );
  while ( ( slot = (Slot*)li.getNext() ) )
  {
    if ( ( slot->min <= x ) && ( slot->max >= x ) )
      return x;
    if ( ( slot->min >= x ) && ( left ) )
    {
      // this assert says that we can't request something less
      // than INT_MIN and that before advancing min past x, we
      // would have to have gone thru the loop at least 1 time.
      ASSERT( prev );
      return prev->max - 5;
    }
    else if ( ( slot->min > x ) && ( !left ) )
    {
      return slot->min + 5;
    }
    prev = slot;
  }
  li.setList( *this );
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    fprintf( stdout, "%s[%d] failed %d (%x)\n", __FILE__, __LINE__, x, left );
    while ( slot = (Slot*)li.getNext() )
    {
      fprintf( stdout, "\t %d <--> %d\n", slot->min, slot->max );
    }
  }
#endif

  ASSERT( FALSE );
  return 0;
}

//
// split a Slot
//
void SlotList::occupy( int x, int width )
{
  int size = this->getSize();
  Slot* slot;
  int found = 0;
  int i;
  for ( i = 1; i <= size; i++ )
  {
    slot = (Slot*)this->getElement( i );
    if ( ( slot->min <= x ) && ( slot->max >= x ) )
    {
      found = i;
      break;
    }
  }
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    if ( !found )
    {
      for ( i = 1; i <= size; i++ )
      {
        slot = (Slot*)this->getElement( i );
        fprintf( stdout, "\t %d - %d\n", slot->min, slot->max );
      }
    }
  }
#endif
  ASSERT( found );

  int right = x + width;
  if ( right < slot->max )
  {
    int old_max = slot->max;
    slot->max = x;
    this->insertElement( new Slot( right, old_max ), found + 1 );
  }
  else
  {
    slot->max = x;
    Slot* prev = NUL( Slot* );
    List to_delete;
    for ( i = found + 1; i <= size; i++ )
    {
      slot = (Slot*)this->getElement( i );
      if ( slot->max > right )
      {
        if ( slot->min < right )
        {
          slot->min = right;
        }
        else
        {
#if defined( DEBUG_PLACEMENT )
          if ( debug )
          {
            fprintf( stdout, "%s[%d] Warning, splitting a slot failed\n",
                     __FILE__, __LINE__ );
            Slot* s;
            for ( int j = 1; j <= size; j++ )
            {
              s = (Slot*)this->getElement( j );
              fprintf( stdout, "\t %d to %d\n", s->min, s->max );
            }
          }
#endif
        }
        break;
      }
      else
      {
        to_delete.appendElement( slot );
      }
      prev = slot;
    }
    ListIterator iter( to_delete );
    while ( ( slot = (Slot*)iter.getNext() ) )
    {
      ASSERT( this->removeElement( slot ) );
      delete slot;
    }
  }
}

//
// 3) Starting with the middle node in the sorted list, position each
//    above its destination or in the case of node traveling more than 1 hop,
//    above a space between nodes, or place the node directly above its
// destination
//    if that is available.
//
void LayoutRow::layout( SlotList* slots, GraphLayout* mgr, int& previous_id )
{
  int size = this->nodes.getSize();
  int middle = ( size >> 1 );
  int i, left_edge, right_edge;

  //
  // The decision to err on the side of {left,right}-wards movment is made
  // based on the location of the destination's input tab.  If the tab is more
  // than half-way across the standIn, then we favor moving right.
  //
  NodeInfo* info = (NodeInfo*)this->node_array[middle]->getLayoutInformation();
  boolean go_left = this->favorsLeftShift( info->getDestination(), mgr, TRUE );

  if ( go_left )
  {
    left_edge = -9999999;  // could also be INT_MIN, INT_MAX
    right_edge = 9999999;
  }
  else
  {
    left_edge = 9999999;  // could also be INT_MIN, INT_MAX
    right_edge = -9999999;
  }

  this->position( this->node_array[middle], left_edge, right_edge, mgr, go_left,
                  slots, previous_id );

  int saved_left_edge = left_edge;
  int saved_right_edge = right_edge;

  // for each node left and right of center
  go_left = TRUE;
  for ( i = middle - 1; i >= 0; i-- )
  {
    this->position( this->node_array[i], left_edge, right_edge, mgr, go_left,
                    slots, previous_id );
  }
  go_left = FALSE;
  left_edge = saved_left_edge;
  right_edge = saved_right_edge;
  for ( i = middle + 1; i < size; i++ )
  {
    this->position( this->node_array[i], left_edge, right_edge, mgr, go_left,
                    slots, previous_id );
  }

  previous_id = this->getId();
}
void LayoutRow::position( Node* n, int& left_edge, int& right_edge,
                          GraphLayout* lay, boolean go_left, SlotList* slots,
                          int previous_id )
{
  int half_tab_width = 9;
  int x, y, dx, dy, w, h;
  NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
  info->getXYSize( w, h );
  int offset = 0;
  Ark* arc = info->getDestination();
  int hop;
  int output;
  arc->getSourceNode( output );

  StandIn* si = n->getStandIn();
  int tabx = si->getOutputParameterTabX( output );
  int xcoord_of_line = info->getDestinationLocation( hop );
  ASSERT( hop > info->getGraphDepth() );
  if ( go_left )
  {
    int desired_right_edge = xcoord_of_line + w - ( tabx + half_tab_width );
    if ( ( left_edge - REQUIRED_HSEP ) > desired_right_edge )
    {
    }
    else if ( ( left_edge - GraphLayout::NodeSpacing ) < desired_right_edge )
    {
      offset = ( left_edge - GraphLayout::NodeSpacing ) - desired_right_edge;
    }
  }
  else
  {
    int desired_left_edge = xcoord_of_line - ( half_tab_width + tabx );
    if ( ( right_edge + REQUIRED_HSEP ) < desired_left_edge )
    {
    }
    else if ( ( right_edge + GraphLayout::NodeSpacing ) > desired_left_edge )
    {
      offset = ( right_edge + GraphLayout::NodeSpacing ) - desired_left_edge;
    }
  }
  //
  // If we can make the arc straight, then notify the destination that
  // he has achieved straightness and doesn't need to have his incoming
  // arcs further straightened, which will happen post-layout in
  // LayoutGroup::straightenArcs();
  //
  int dummy;
  Node* dest = arc->getDestinationNode( dummy );
  NodeInfo* dinfo = (NodeInfo*)dest->getLayoutInformation();

  int target_x = xcoord_of_line + offset;
  // If we're wired to something on the previous row which is usually 1 hop
  // down.
  // It could also be that the 2 nodes could be like Supervise{State,Window}
  // with
  // much different hop counts but with no intervening rows.
  if ( ( hop == ( info->getGraphDepth() + 1 ) ) || ( hop == previous_id ) )
  {
    if ( lay->positionSource( info->getDestination(), target_x ) )
    {
#if defined( DEBUG_PLACEMENT )
      if ( debug )
      {
        fprintf( stdout, "%s[%d] %s:%d collided\n", __FILE__, __LINE__,
                 n->getNameString(), n->getInstanceNumber() );
      }
#endif
    }
    dinfo->registerStraightArc( offset, arc );
  }
  else
  {
    int available_x = slots->isAvailable( target_x, go_left );
    if ( lay->positionSource( info->getDestination(), available_x ) )
    {
#if defined( DEBUG_PLACEMENT )
      if ( debug )
      {
        fprintf( stdout, "%s[%d] %s:%d collided\n", __FILE__, __LINE__,
                 n->getNameString(), n->getInstanceNumber() );
      }
#endif
    }
    dinfo->registerStraightArc( available_x - xcoord_of_line, arc );
  }
  info->getXYPosition( x, y );
#if defined( DEBUG_PLACEMENT )
  if ( debug )
  {
    fprintf( stdout, "%s[%d] %s:%d placed at %d,%d occupies %d to %d\n",
             __FILE__, __LINE__, n->getNameString(), n->getInstanceNumber(), x,
             y, x, x + w );
  }
#endif
  // What's the meaning of the -3,+6?  Really only the space from x to x+w is
  // occupied.  Nevertheless, the line router won't place a line closer to
  // a node than 3 pixels.  So we pretend that we're occupying 3 pixels
  // either side of the left and right edges.  That way we won't try to
  // use those areas in a subsequent pass.
  this->slot_list.occupy( x - 3, w + 6 );
  left_edge = x;
  right_edge = x + w;
}

int NodeInfo::getDestinationLocation( int& hop )
{
  int input;
  Node* dst = this->destination->getDestinationNode( input );
  NodeInfo* dinfo = (NodeInfo*)dst->getLayoutInformation();
  hop = dinfo->getGraphDepth();
  StandIn* si = dst->getStandIn();
  int half_tab_width = 9;
  int dx, dy;
  dinfo->getXYPosition( dx, dy );
  int tabx = si->getInputParameterTabX( input );
  return tabx + dx + half_tab_width;
}

int LayoutGroup::SortByHop( const void* a, const void* b )
{
  Node** aptr = (Node**)a;
  Node** bptr = (Node**)b;
  Node* anode = (Node*)*aptr;
  Node* bnode = (Node*)*bptr;
  NodeInfo* ainfo = (NodeInfo*)anode->getLayoutInformation();
  NodeInfo* binfo = (NodeInfo*)bnode->getLayoutInformation();

  // descending order of hop count
  int ahops = ainfo->getGraphDepth();
  int bhops = binfo->getGraphDepth();
  if ( ahops > bhops )
    return -1;
  if ( ahops < bhops )
    return 1;
  return 0;
}

int LayoutRow::SortByDestinationX( const void* a, const void* b )
{
  int ainput, binput, dummy;
  Node** aptr = (Node**)a;
  Node** bptr = (Node**)b;
  Node* anode = (Node*)*aptr;
  Node* bnode = (Node*)*bptr;
  NodeInfo* ainfo = (NodeInfo*)anode->getLayoutInformation();
  NodeInfo* binfo = (NodeInfo*)bnode->getLayoutInformation();

  int half_tab_width = 9;
  int ai = ainfo->getDestinationLocation( dummy );  // + half_tab_width;
  int bi = binfo->getDestinationLocation( dummy );  // + half_tab_width;
  if ( ai < bi )
    return -1;
  if ( ai > bi )
    return 1;

  int ahops = ainfo->getGraphDepth();
  int bhops = binfo->getGraphDepth();
  if ( ahops > bhops )
    return -1;
  if ( ahops < bhops )
    return 1;

  return 0;
}

int LayoutRow::SortByX( const void* a, const void* b )
{
  int ainput, binput, ax, bx, dummy;
  Node** aptr = (Node**)a;
  Node** bptr = (Node**)b;
  Node* anode = (Node*)*aptr;
  Node* bnode = (Node*)*bptr;
  NodeInfo* ainfo = (NodeInfo*)anode->getLayoutInformation();
  NodeInfo* binfo = (NodeInfo*)bnode->getLayoutInformation();

  ainfo->getXYPosition( ax, dummy );
  binfo->getXYPosition( bx, dummy );
  if ( ax < bx )
    return -1;
  if ( ax > bx )
    return 1;
  return 0;
}

void GraphLayout::getSpecialAncestorsOf( Node* root, List& ancestors,
                                         List& arcs, boolean last_call )
{
  int input, output;
  int input_count = root->getInputCount();
  int k;
  for ( k = 1; k <= input_count; k++ )
  {
    if ( !root->isInputVisible( k ) )
      continue;
    List* inputs = (List*)root->getInputArks( k );
    if ( !inputs )
      continue;
    ListIterator li( *inputs );
    Ark* arc;
    int dummy;
    while ( ( arc = (Ark*)li.getNext() ) )
    {
      Node* src = arc->getSourceNode( output );
      LayoutInfo* linfo = (LayoutInfo*)src->getLayoutInformation();
      if ( linfo->isPositioned() )
        continue;
      if ( ancestors.isMember( src ) == FALSE )
      {
        const char* name = src->getNameString();
        if ( EqualString( "Get", name ) || EqualString( "GetGlobal", name ) ||
             EqualString( "GetLocal", name ) )
        {
          if ( output != 2 )
            continue;
          arcs.appendElement( arc );
          ancestors.appendElement( src );
          this->getSpecialAncestorsOf( src, ancestors, arcs, FALSE );
        }
        else if ( this->hasNoCloserDescendant( src, root ) )
        {
          // only handle distant ancestor nodes if those node don't
          // have a more closely related descendant.
          arcs.appendElement( arc );
          ancestors.appendElement( src );
          this->getSpecialAncestorsOf( src, ancestors, arcs, FALSE );
        }
      }
    }
  }

  if ( last_call )
  {
    //
    // Examine each arc we've picked.  See if each arc ought to be replaced
    // with a better choice.  A choice is better if the src and dst nodes
    // have multiple arcs and it's more near the center of the set of arcs.
    //
    ListIterator iter( arcs );
    List to_add;
    List to_remove;
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* src = arc->getSourceNode( output );
      Node* dst = arc->getDestinationNode( input );
      int cnt = this->countConnectionsBetween( src, dst );
      if ( cnt <= 2 )
        continue;
      int to_skip = cnt >> 1;
      int skipped = 0;
      input_count = dst->getInputCount();
      boolean changed = FALSE;
      for ( input = 1; input <= input_count; input++ )
      {
        if ( !dst->isInputVisible( input ) )
          continue;
        List* inputs = (List*)dst->getInputArks( input );
        if ( !inputs )
          continue;
        ListIterator li( *inputs );
        Ark* ia;
        while ( ( ia = (Ark*)li.getNext() ) )
        {
          int output2;
          Node* source = ia->getSourceNode( output2 );
          if ( source == src )
          {
            if ( skipped == to_skip )
            {
              if ( ia != arc )
              {
                to_add.appendElement( ia );
                to_remove.appendElement( arc );
#if defined( DEBUG_PLACEMENT )
                if ( debug )
                {
                  fprintf( stdout, "%s[%d] replacing output %d of %s"
                                   " with output %d\n",
                           __FILE__, __LINE__, output, src->getNameString(),
                           output2 );
                }
#endif
              }
              changed = TRUE;
              break;
            }
            skipped++;
          }
        }
        if ( changed )
          break;
      }
    }
    iter.setList( to_remove );
    while ( ( arc = (Ark*)iter.getNext() ) )
      arcs.removeElement( arc );
    iter.setList( to_add );
    while ( arc = (Ark*)iter.getNext() )
      arcs.appendElement( arc );
    ancestors.clear();
    int size = arcs.getSize();
    for ( int i = 1; i <= size; i++ )
    {
      arc = (Ark*)arcs.getElement( i );
      int dummy;
      Node* src = arc->getSourceNode( dummy );
      ancestors.appendElement( src );
    }
  }
}

//
// If we can't decide left vs right, then return the default value
//
boolean LayoutRow::favorsLeftShift( Ark* arc, GraphLayout* mgr,
                                    boolean default_value )
{
  boolean retval = default_value;

  int input, output, nth_tab;
  Node* src = arc->getSourceNode( output );
  Node* dst = arc->getDestinationNode( input );

  int ci = mgr->countConnectedInputs( dst, input, nth_tab );
  int input_count = dst->getInputCount();
  int visible_input_count = 0;
  for ( input = 1; input < input_count; input++ )
  {
    if ( dst->isInputVisible( input ) )
      visible_input_count++;
  }

  if ( nth_tab > ( ci >> 1 ) )
  {
    retval = FALSE;
  }
  else if ( input > ( visible_input_count >> 1 ) )
  {
    retval = FALSE;
  }

  return retval;
}

void SlotList::clear()
{
  ListIterator iter( *this );
  Slot* slot;
  while ( ( slot = (Slot*)iter.getNext() ) )
    delete slot;
  this->List::clear();
  this->appendElement( new Slot( -999999, 999999 ) );
}

int GraphLayout::countConnectionsBetween( Node* source, Node* dest,
                                          boolean count_consecutive )
{
  int output_count = source->getOutputCount();
  int output, input;
  int connections = 0;
  int prev = -1;
  for ( output = 1; output <= output_count; output++ )
  {
    if ( !source->isOutputVisible( output ) )
      continue;
    List* arks = (List*)source->getOutputArks( output );
    if ( !arks )
      continue;
    ListIterator iter( *arks );
    Ark* arc;
    while ( ( arc = (Ark*)iter.getNext() ) )
    {
      Node* destination = arc->getDestinationNode( input );
      if ( destination == dest )
      {
        if ( count_consecutive )
        {
          connections++;
        }
        else
        {
          int nth_tab;
          this->countConnectedInputs( destination, input, nth_tab );
          if ( nth_tab != ( prev + 1 ) )
          {
            connections++;
          }
          prev = nth_tab;
        }
      }
    }
  }
  return connections;
}

//
// Starting with the nodes at the top, try to shift them out farther in order
// to straighten some arc.  Nodes that get in the way are in turn
// shifted outward providing more space.
//
boolean LayoutGroup::straightenArcs( LayoutRow* row_array[], int rows )
{
  boolean retval = FALSE;

  for ( int i = rows - 1; i >= 0; i-- )
  {
    LayoutRow* row = row_array[i];
    row->straightenArcs( retval );
  }
  return retval;
}

void LayoutRow::straightenArcs( boolean& changes_made_on_previous_row )
{
  if ( !this->sorted_by_x )
  {
    qsort( this->node_array, this->nodes.getSize(), sizeof( Node* ),
           LayoutRow::SortByX );
    this->sorted_by_x = TRUE;
    this->sorted_by_destination_x = FALSE;
  }

  boolean changes_made = changes_made_on_previous_row;
  boolean changes_made_on_current_row = FALSE;

  int input, output;
  int size = this->nodes.getSize();
  int midpt = size >> 1;
  for ( int j = 0; j < size; j++ )
  {
    Node* dest = this->node_array[j];
    NodeInfo* dinfo = (NodeInfo*)dest->getLayoutInformation();
    Ark* arc;
    int offset;
    arc = dinfo->hasStraightArc( offset );
    if ( arc == NUL(Ark*))
      continue;

    //
    // problem right here is that, the value we've recorded for
    // offset might not be correct any more if the src node was
    // moved in an earlier pass. FIXME
    //
    if ( ( !changes_made ) && ( !offset ) )
      continue;

    ASSERT( dest == arc->getDestinationNode( input ) );
    Node* src = arc->getSourceNode( output );
    NodeInfo* sinfo = (NodeInfo*)src->getLayoutInformation();

    int sx, sy;
    sinfo->getXYPosition( sx, sy );
    int dx, dy;
    dinfo->getXYPosition( dx, dy );

    //
    // Compute the amount the dest has to shift in order to straighten
    // the arc.  This is based on the the locations of the standIns and
    // the relative locations of their input and output tabs.
    //
    StandIn* ssi = src->getStandIn();
    StandIn* dsi = dest->getStandIn();
    int dtx = dsi->getInputParameterTabX( input );
    int stx = ssi->getOutputParameterTabX( output );

    int delta = -( ( dx + dtx ) - ( sx + stx ) );
    int end, incr;

    if ( delta < 0 )
    {
      end = -1;
      incr = -1;
    }
    else if ( delta > 0 )
    {
      end = size;
      incr = 1;
    }
    else
    {
      dinfo->registerStraightArc( 0, arc );
      continue;
    }

    for ( int k = j; k != end; k += incr )
    {
      Node* n = this->node_array[k];
      NodeInfo* info = (NodeInfo*)n->getLayoutInformation();
#if defined( DEBUG_PLACEMENT )
      if ( debug )
      {
        if ( k == j )
        {
          fprintf( stdout, "%s[%d] moving %s:%d %d row(%d)\n", __FILE__,
                   __LINE__, n->getNameString(), n->getInstanceNumber(), delta,
                   this->getId() );
        }
        else
        {
          fprintf( stdout, "\tmoving %s:%d \n", n->getNameString(),
                   n->getInstanceNumber() );
        }
      }
#endif
      info->getXYPosition( dx, dy );
      int dx2 = dx + delta;
      info->setProposedLocation( dx2, dy );

      //
      // continue scooting neighbors over until we have created enough
      // whitespace so that it's no longer necessary.
      //
      boolean keep_scooting = TRUE;

      int nextk = k + incr;
      if ( nextk != end )
      {
        Node* nn = this->node_array[nextk];
        int nnx, nny;
        NodeInfo* nninfo = (NodeInfo*)nn->getLayoutInformation();
        nninfo->getXYPosition( nnx, nny );
        if ( incr > 0 )
        {
          // does the right edge of n encroach on the left edge of nn
          int dw, dh;
          info->getXYSize( dw, dh );
          if ( ( dx2 + dw + REQUIRED_HSEP ) < nnx )
            keep_scooting = FALSE;
        }
        else
        {
          // does the left edge of n encroach on the right edge of nn
          int nnw, nnh;
          nninfo->getXYSize( nnw, nnh );
          if ( ( nnx + nnw + REQUIRED_HSEP ) < dx2 )
            keep_scooting = FALSE;
        }
      }

      if ( !keep_scooting )
        break;
    }
    changes_made = TRUE;
    changes_made_on_current_row = TRUE;
  }
  if ( !changes_made_on_current_row )
    changes_made = FALSE;
}

Ark* NodeInfo::hasStraightArc( int& offset )
{
  if ( !this->straightness_set )
    return NUL( Ark* );
  offset = this->offset_for_straightness;
  return this->straightness_opportunity;
}

void NodeInfo::registerStraightArc( int offset, Ark* arc )
{
  int dummy;
  Node* src;
  NodeInfo* sinfo;

  //
  // The this is the info for the node at the destination end of arc
  //
  if ( !this->straightness_set )
  {
    this->offset_for_straightness = offset;
    this->straightness_opportunity = arc;
    this->straightness_set = TRUE;

    src = arc->getSourceNode( dummy );
    sinfo = (NodeInfo*)src->getLayoutInformation();
    sinfo->setStraightnessDestination( this );

    return;
  }
  if ( abs( offset ) < abs( this->offset_for_straightness ) )
  {
    this->offset_for_straightness = offset;

    src = arc->getSourceNode( dummy );
    sinfo = (NodeInfo*)src->getLayoutInformation();
    sinfo->setStraightnessDestination( NUL(NodeInfo*));
    this->straightness_opportunity = arc;

    // find the NodeInfo at the src end of the arc.
    // Notify that object that this of a partnership.
    src = arc->getSourceNode( dummy );
    sinfo = (NodeInfo*)src->getLayoutInformation();
    sinfo->setStraightnessDestination( this );
  }
}

//
// The purpose for shiftStraightArc(), setStraightnessDestination(),
// and a virtual setProposedLocation() is to modify our notion
// of straightness so that if a src is moved in order to straighten
// one of its incoming arcs, we'll notify downstream arcs that had
// once believed themselves to be straight, that they're no longer
// straight.  All these methods are used as a result of ::straightenArcs().
// Note that by storing a reference to a NodeInfo* inside the
// NodeInfo* object we create a potential crash bug if that NodeInfo*
// is deleted.
//
void NodeInfo::shiftStraightArc( int dx )
{
  if ( !this->straightness_set )
    return;
  this->offset_for_straightness += dx;
}

void NodeInfo::setProposedLocation( int x, int y )
{
  int dx;
  boolean was_positioned = this->positioned_yet;

  if ( was_positioned )
    dx = x - this->x;

  this->LayoutInfo::setProposedLocation( x, y );
  if ( !was_positioned )
    return;

  //
  // If the destination is using this node as it's
  // targeted straight arc and the destination thought
  // that the arc was stragith, then ensure that the
  // destination knows that it's arc isn't straight
  // any longer.
  //
  if ( this->straightness_destination )
    this->straightness_destination->shiftStraightArc( dx );
}

void NodeInfo::setStraightnessDestination( NodeInfo* dest )
{
  this->straightness_destination = dest;
}
